vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Maheshmati and Sangu are playing a game. First, Maheshmati gives Sangu a sequence of $N$ distinct integers $a_1, a_2, \dots, a_N$ (not necessarily sorted) and an integer $K$. Sangu has to create all subsequences of this sequence with length $K$. For each subsequence, he has to write down the product of $K-2$ integers: all elements of this subsequence except the minimum and maximum element.
Sangu wins the game if he is able to write down all these numbers and tell Maheshmati their product (modulo $10^9+7$, since it can be very large). However, Sangu is a very lazy child and thus wants you to help him win this game. Compute the number Sangu should tell Maheshmati!

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $K$.
- The second line contains $N$ space-separated integers $a_1, a_2, \dots, a_N$.

-----Output-----
For each test case, print a single line containing one integer — the product of all numbers written down by Sangu modulo $10^9+7$.

-----Constraints-----
- $1 \le T \le 10$
- $3 \le N \le 5,000$
- $3 \le K \le N$
- $1 \le a_i \le 10,000$ for each valid $i$
- the numbers $a_1, a_2, \dots, a_N$ are pairwise distinct

-----Subtasks-----
Subtask #1 (20 points): $1 \le N \le 10$
Subtask #2 (80 points): original constraints

-----Example Input-----
1
4 3 
1 2 3 4 

-----Example Output-----
36

-----Explanation-----
Example case 1: There are four possible subsequences:
- $[1, 2, 3]$ (Sangu should write down $2$.)
- $[1, 3, 4]$ (Sangu should write down $3$.)
- $[1, 2, 4]$ (Sangu should write down $2$.)
- $[2, 3, 4]$ (Sangu should write down $3$.)
The required product is $2 \cdot 3 \cdot 2 \cdot 3 = 36$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider a Deterministic Finite Automaton(DFA) which takes N states numbered from 0 to N-1, with alphabets 0 and 1. Now consider a string of 0s and 1s, let the decimal value of this string as M. For e.g., if string be "010" then the decimal value or M is 2. The speciality in our DFA is that when we simulate the string through this DFA, it finally takes us to the state with the same number as of M%N, where % is the modulus operator. For e.g. if our string is "1100" i.e. M is 12 and N is 5, then after simulating this string through DFA, it will reach to state 12%5 i.e. state no. 2. Since M%N can be any number from 0 to N-1, and the states in our DFA are also from 0 to N-1, there must always be some state we will reach. Assume the starting state of DFA is 0.

You are given N, the no. of states in our DFA. Print a transition table for this DFA.

Input

An integer N

Output

Output the N lines where i-th line will contain 3 space-separated integers a b c where 

a=(i-1), 

b is the state no. where state no. a takes us to, for input alphabet 0

c is the state no. where state no. a takes us to, for input alphabet 1

i.e. i-th line will show the transition of state no. (i-1)

Constraints

1 ≤ N ≤ 100

SAMPLE INPUT
5

SAMPLE OUTPUT
0 0 1
1 2 3
2 4 0
3 1 2
4 3 4

Explanation

Lets take the above example with string "1100" and N=5,

Initially we are at state no. 0 (given).
After reading '1' of our string, we goes to state no. 1 (1st line of output tells about transition from state no. 0)
After reading the next '1', we goes to state no. 3 (2nd line of output)
After reading '0' of our string, we goes to state no. 1 (4th line of output)
After reading the final input alphabet i.e. '0', we goes to state no. 2. and that is also 12%5.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef calls a number *lucky* if it contains the digit 7 at least once. 

Given a number X, determine if it is a *lucky* number or not.

------ Input Format ------ 

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first and only line of each test case contains an integer X — the number mentioned in the problem statement.

------ Output Format ------ 

For each test case, output YES if X is a lucky number. Otherwise, output NO.

You may print each character of YES and NO in uppercase or lowercase (for example, yes, yEs, Yes will be considered identical).

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤X ≤10^{9}$

----- Sample Input 1 ------ 
4
6
478
2090
77777

----- Sample Output 1 ------ 
NO
YES
NO
YES

----- explanation 1 ------ 
Test Case 1: The number $6$ is not lucky since it does not contain the digit $7$.

Test Case 2: The number $478$ is lucky since it contains the digit $7$ at least once.

Test Case 3: The number $2090$ is not lucky since it does not contain the digit $7$.

Test Case 4: The number $77777$ is lucky since it contains the digit $7$ at least once.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have a team of N people. For a particular task, you can pick any non-empty subset of people. The cost of having x people for the task is x^{k}. 

Output the sum of costs over all non-empty subsets of people.


-----Input-----

Only line of input contains two integers N (1 ≤ N ≤ 10^9) representing total number of people and k (1 ≤ k ≤ 5000).


-----Output-----

Output the sum of costs for all non empty subsets modulo 10^9 + 7.


-----Examples-----
Input
1 1

Output
1

Input
3 2

Output
24



-----Note-----

In the first example, there is only one non-empty subset {1} with cost 1^1 = 1.

In the second example, there are seven non-empty subsets.

- {1} with cost 1^2 = 1

- {2} with cost 1^2 = 1

- {1, 2} with cost 2^2 = 4

- {3} with cost 1^2 = 1

- {1, 3} with cost 2^2 = 4

- {2, 3} with cost 2^2 = 4

- {1, 2, 3} with cost 3^2 = 9

The total cost is 1 + 1 + 4 + 1 + 4 + 4 + 9 = 24.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problem statements in [Russian] and [Mandarin Chinese].

Value of an array A of length L is defined as the sum of (A_{i} \oplus i) for all 0 ≤ i < L, where \oplus denotes [bitwise xor operation]. Note that array indices start from zero.
 
You are given an integer N and an array A consisting of 2^{N} integers where A_{i} = i for all 0 ≤ i < 2^{N}.
 
Example :
For N = 1, you have an array A of length 2^{1} = 2 and A = [0, 1].
For N = 2, you have an array A of length 2^{2} = 4 and A = [0, 1, 2, 3].

You can do at most K operations on this array. In one operation, you can choose two indices i and j (0 ≤ i, j < 2^{N}) and swap A_{i} and A_{j} (i.e. A_{i} becomes A_{j} and vice versa). 

What is the maximum value of array A you can obtain after at most K operations? 

------ Input Format ------ 

- First line will contain T, number of testcases. Then the testcases follow.
- Each testcase contains a single line of input, two integers N, K.

------ Output Format ------ 

For each testcase, output in a single line the maximum value of array after doing at most K operations.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 30$
$0 ≤ K ≤ 10^{9}$

----- Sample Input 1 ------ 
3
2 0
2 1
10 100
----- Sample Output 1 ------ 
0
6
204600
----- explanation 1 ------ 
- In the first test case, for $N = 2$, you have the array $A = [0, 1, 2, 3]$. No swap operation is 
allowed hence value of array $A = (0 \oplus 0) + (1 \oplus 1) + (2 \oplus 2) + (3 \oplus 3) = 0 + 0 + 0 + 0 = 0$. 
- In the second test case, initially the array $A = [0, 1, 2, 3]$. If you swap $A_{1}$ and $A_{2}$, $A$ becomes $[0, 2, 1, 3]$. Now value of array $A = (0 \oplus 0) + (2 \oplus 1) + (1 \oplus 2) + (3 \oplus 3) = 0 + 3 + 3 + 0 = 6$. There is no possible way such that value of array $A$ becomes greater than $6$ using one swap operation.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Heidi enjoyed performing the simulation because she knew exactly when a new universe would be formed and where, and when a non-existent link would be broken and where.

However, the multiverse itself works in mysterious ways. Well, it works using probabilities, which to some people is mysterious.

At each unit time, when a decision is made, one of the two events will happen randomly. Let's denote l as the current length of the multiverse. With a probability of p_{create} = 1 - l/m, a universe will be created. With a probability of p_{break}=l/m, a non-existent link will be broken at some position.

More specifically, 

  * When a universe is created, it will manifest itself between any two adjacent universes or at one of the ends. Each position occurs with a probability of (1)/(l + 1). 
  * When a link is broken, it could be cut between any two adjacent universes, each with a probability of (1)/(l-1). After separating the multiverse into two segments, the segment NOT containing the Doctor will cease to exist. 



As earlier, the Doctor remains in the same universe. However, if at some point the multiverse breaks in such a way that the Doctor finds himself at the leftmost or rightmost end of it, the TARDIS stops functioning.

In such a case, the Doctor must actually walk across the multiverse to find the tools to fix it.

We are interested in the expected value of the length of the multiverse when such an event occurs.

Input

The first and only line contains three integers n, k and m (1 ≤ k ≤ n ≤ m ≤ 250), the initial length of the multiverse, the initial position of the Doctor, and the maximum possible length of the multiverse.

Output

Output a single integer on a single line, indicating the expected length of the multiverse.

If the answer is p/q, please print r where p ≡ r ⋅ q (mod  10^9 + 7).

Examples

Input


2 1 2


Output


2


Input


2 2 10


Output


2


Input


3 2 3


Output


2


Input


3 2 5


Output


941659828


Input


10 4 20


Output


196683114

Note

For the first and the second test case, without any change to the multiverse, the Doctor is already at one of the ends.

For the third test case, the multiverse can only break at a position, which renders the Doctor at one of its ends.

For the fourth case, things seem to be a little more complicated, because the multiverse can grow and then be broken again.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N toffies in a room labelled from 1 to N and there are  N - 1 directed path between these toffies such that every toffy has at least 1 path leading to the toffy or away from it.

K and L want to eat all the toffies in the room but they don't know where to start.

If K starts with the toffy labelled c (1 ≤ c ≤ N), then he can eat all the toffies which can be reached from the position of the toffy c. Similarly, if L starts with the toffy labelled d (1 ≤ d ≤ N), then he can eat all the toffies which can be reached from the position of the toffy d. Note that both, K and L, can start from the same toffy position.

Now, they will be able to eat all the toffies in the room if there exist toffy positions c and d such that any other toffy in the room can be eaten by at least one of them. In order to make this possible, they want to change the direction of some number of paths. You have to calculate the minimum number of paths that need to be changed so that K and L can eat all the toffies.

Input Format

The first line of input contains the number of toffies, N(1 ≤ N ≤ 3000). Each of the next N-1 lines contains 2 space separated integers ai and bi (1 ≤ ai,bi ≤ N; ai != bi) denoting that there exists a directed path from toffy ai to toffy bi. Toffies are labeled from 1 to N.

Output Format

In the only line of output print the minimum number of paths that need to be changed so that K and L can eat all the toffies.

SAMPLE INPUT
4
1 4
2 4
3 4

SAMPLE OUTPUT
1

Explanation

In the sample case, the graph is such that we need to change at least one path to achieve our target. One of the possible ways is to reverse the path from (1, 4) to (4, 1) and then select C, D as 2, 3 respectively.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: The New Year: Meeting Friends

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There are three friend living on the straight line *Ox* in Lineland. The first friend lives at the point *x*1, the second friend lives at the point *x*2, and the third friend lives at the point *x*3. They plan to celebrate the New Year together, so they need to meet at one point. What is the minimum total distance they have to travel in order to meet at some point and celebrate the New Year?

It's guaranteed that the optimal answer is always integer.

Input Specification:
The first line of the input contains three distinct integers *x*1, *x*2 and *x*3 (1<=≤<=*x*1,<=*x*2,<=*x*3<=≤<=100) — the coordinates of the houses of the first, the second and the third friends respectively.

Output Specification:
Print one integer — the minimum total distance the friends need to travel in order to meet together.

Demo Input:
['7 1 4\n', '30 20 10\n']

Demo Output:
['6\n', '20\n']

Note:
In the first sample, friends should meet at the point 4. Thus, the first friend has to travel the distance of 3 (from the point 7 to the point 4), the second friend also has to travel the distance of 3 (from the point 1 to the point 4), while the third friend should not go anywhere because he lives at the point 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Subway Innovation

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Berland is going through tough times — the dirt price has dropped and that is a blow to the country's economy. Everybody knows that Berland is the top world dirt exporter!

The President of Berland was forced to leave only *k* of the currently existing *n* subway stations.

The subway stations are located on a straight line one after another, the trains consecutively visit the stations as they move. You can assume that the stations are on the *Ox* axis, the *i*-th station is at point with coordinate *x**i*. In such case the distance between stations *i* and *j* is calculated by a simple formula |*x**i*<=-<=*x**j*|.

Currently, the Ministry of Transport is choosing which stations to close and which ones to leave. Obviously, the residents of the capital won't be too enthusiastic about the innovation, so it was decided to show the best side to the people. The Ministry of Transport wants to choose such *k* stations that minimize the average commute time in the subway!

Assuming that the train speed is constant (it is a fixed value), the average commute time in the subway is calculated as the sum of pairwise distances between stations, divided by the number of pairs (that is ) and divided by the speed of the train.

Help the Minister of Transport to solve this difficult problem. Write a program that, given the location of the stations selects such *k* stations that the average commute time in the subway is minimized.

Input Specification:
The first line of the input contains integer *n* (3<=≤<=*n*<=≤<=3·105) — the number of the stations before the innovation. The second line contains the coordinates of the stations *x*1,<=*x*2,<=...,<=*x**n* (<=-<=108<=≤<=*x**i*<=≤<=108). The third line contains integer *k* (2<=≤<=*k*<=≤<=*n*<=-<=1) — the number of stations after the innovation.

The station coordinates are distinct and not necessarily sorted.

Output Specification:
Print a sequence of *k* distinct integers *t*1,<=*t*2,<=...,<=*t**k* (1<=≤<=*t**j*<=≤<=*n*) — the numbers of the stations that should be left after the innovation in arbitrary order. Assume that the stations are numbered 1 through *n* in the order they are given in the input. The number of stations you print must have the minimum possible average commute time among all possible ways to choose *k* stations. If there are multiple such ways, you are allowed to print any of them.

Demo Input:
['3\n1 100 101\n2\n']

Demo Output:
['2 3 ']

Note:
In the sample testcase the optimal answer is to destroy the first station (with *x* = 1). The average commute time will be equal to 1 in this way.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Abhi Ram analyses london stock exchange and invests in a software company C-.gate . He wants to sell his shares after 5 weeks.

Given the investment  m, increase or decrease of share prices of 5 weeks(+/- pi) , help him to calculate his net profit or loss percentage(n%) of his investment to establish his own company KMC.

-----Input:-----

- The first line contains an integer T which denotes the number of test cases.
- Each test case comprises of two lines: the first line contains the integer m which denotes the amount invested.

The second line consists of five space separated integers(p1, p2, p3, p4, p5) each preceeded by + (increase) or - (decrease) which give the percentage of change in share prices over 5 weeks.
.

-----Output:-----
The output contains a single number n which gives the percentage of profit or loss preceeded by + (profit) or - (loss).

-----Constraints:-----
- 1 ≤ T ≤ 100
- 1 ≤ m ≤ 105
- -100 ≤ pi ≤ 100

-----Example:-----
Input:
2
10000
+5 -3 -2 +10 +15
6256250
-24 +22 +4 -16 +20

Output:
+26.2634
-2.79977

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You and your friend are playing the game Mortal Kombat XI. You are trying to pass a challenge tower. There are $n$ bosses in this tower, numbered from $1$ to $n$. The type of the $i$-th boss is $a_i$. If the $i$-th boss is easy then its type is $a_i = 0$, otherwise this boss is hard and its type is $a_i = 1$.

During one session, either you or your friend can kill one or two bosses (neither you nor your friend can skip the session, so the minimum number of bosses killed during one session is at least one). After your friend session, your session begins, then again your friend session begins, your session begins, and so on. The first session is your friend's session.

Your friend needs to get good because he can't actually kill hard bosses. To kill them, he uses skip points. One skip point can be used to kill one hard boss.

Your task is to find the minimum number of skip points your friend needs to use so you and your friend kill all $n$ bosses in the given order.

For example: suppose $n = 8$, $a = [1, 0, 1, 1, 0, 1, 1, 1]$. Then the best course of action is the following:

  your friend kills two first bosses, using one skip point for the first boss;  you kill the third and the fourth bosses;  your friend kills the fifth boss;  you kill the sixth and the seventh bosses;  your friend kills the last boss, using one skip point, so the tower is completed using two skip points. 

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of bosses. The second line of the test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 1$), where $a_i$ is the type of the $i$-th boss.

It is guaranteed that the sum of $n$ does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$).


-----Output-----

For each test case, print the answer: the minimum number of skip points your friend needs to use so you and your friend kill all $n$ bosses in the given order.


-----Example-----
Input
6
8
1 0 1 1 0 1 1 1
5
1 1 1 1 0
7
1 1 1 1 0 0 1
6
1 1 1 1 1 1
1
1
1
0

Output
2
2
2
2
1
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two positive integer numbers x and y. An array F is called an y-factorization of x iff the following conditions are met:  There are y elements in F, and all of them are integer numbers;  $\prod_{i = 1}^{y} F_{i} = x$. 

You have to count the number of pairwise distinct arrays that are y-factorizations of x. Two arrays A and B are considered different iff there exists at least one index i (1 ≤ i ≤ y) such that A_{i} ≠ B_{i}. Since the answer can be very large, print it modulo 10^9 + 7.


-----Input-----

The first line contains one integer q (1 ≤ q ≤ 10^5) — the number of testcases to solve.

Then q lines follow, each containing two integers x_{i} and y_{i} (1 ≤ x_{i}, y_{i} ≤ 10^6). Each of these lines represents a testcase.


-----Output-----

Print q integers. i-th integer has to be equal to the number of y_{i}-factorizations of x_{i} modulo 10^9 + 7.


-----Example-----
Input
2
6 3
4 2

Output
36
6



-----Note-----

In the second testcase of the example there are six y-factorizations:  { - 4,  - 1};  { - 2,  - 2};  { - 1,  - 4};  {1, 4};  {2, 2};  {4, 1}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dexterina and Womandark have been arch-rivals since they’ve known each other. Since both are super-intelligent teenage girls, they’ve always been trying to solve their disputes in a peaceful and nonviolent way. After god knows how many different challenges they’ve given to one another, their score is equal and they’re both desperately trying to best the other in various games of wits. This time, Dexterina challenged Womandark to a game of Nim.

Nim is a two-player game in which players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object, and may remove any number of objects from a single heap. The player who can't make a turn loses. By their agreement, the sizes of piles are selected randomly from the range [0, x]. Each pile's size is taken independently from the same probability distribution that is known before the start of the game.

Womandark is coming up with a brand new and evil idea on how to thwart Dexterina’s plans, so she hasn’t got much spare time. She, however, offered you some tips on looking fabulous in exchange for helping her win in Nim. Your task is to tell her what is the probability that the first player to play wins, given the rules as above.

Input

The first line of the input contains two integers n (1 ≤ n ≤ 109) and x (1 ≤ x ≤ 100) — the number of heaps and the maximum number of objects in a heap, respectively. The second line contains x + 1 real numbers, given with up to 6 decimal places each: P(0), P(1), ... , P(X). Here, P(i) is the probability of a heap having exactly i objects in start of a game. It's guaranteed that the sum of all P(i) is equal to 1.

Output

Output a single real number, the probability that the first player wins. The answer will be judged as correct if it differs from the correct answer by at most 10 - 6.

Example

Input

2 2
0.500000 0.250000 0.250000


Output

0.62500000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.