apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
The girl Umka loves to travel and participate in math olympiads. One day she was flying by plane to the next olympiad and out of boredom explored a huge checkered sheet of paper.

Denote the $$$n$$$-th Fibonacci number as $$$F_n = \begin{cases} 1, & n = 0; \\ 1, & n = 1; \\ F_{n-2} + F_{n-1}, & n \ge 2. \end{cases}$$$

A checkered rectangle with a height of $$$F_n$$$ and a width of $$$F_{n+1}$$$ is called a Fibonacci rectangle of order $$$n$$$.

Umka has a Fibonacci rectangle of order $$$n$$$. Someone colored a cell in it at the intersection of the row $$$x$$$ and the column $$$y$$$.

It is necessary to cut this rectangle exactly into $$$n+1$$$ squares in such way that

- the painted cell was in a square with a side of $$$1$$$;
- there was at most one pair of squares with equal sides;
- the side of each square was equal to a Fibonacci number.

Will Umka be able to cut this rectangle in that way?

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — number of test cases.

For each test case the integers $$$n$$$, $$$x$$$, $$$y$$$ are given ($$$1 \le n \le 44$$$, $$$1 \le x \le F_n$$$, $$$1 \le y \le F_{n+1}$$$) — the order of the Fibonacci rectangle and the coordinates of the colored cell.

## Output Format
For each test case, print "YES" if the answer is positive, and "NO" otherwise.

You can print "YES" and "NO" in any case (for example, the strings "yEs", "yes" and "Yes" will be recognized as a positive answer).

## Examples
```input
12
1 1 1
2 1 2
3 1 4
3 3 2
4 4 6
4 3 3
5 6 5
5 4 12
5 2 12
4 2 1
1 1 2
44 758465880 1277583853
```
```output
YES
NO
YES
YES
YES
NO
YES
NO
NO
YES
YES
NO
```

## Note
The first, third and fourth test cases.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
In Japan, the number $$$4$$$ reads like death, so Bob decided to build a live sequence. Living sequence $$$a$$$ contains all natural numbers that do not contain the digit $$$4$$$. $$$a = [1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16, \ldots]$$$.

For example, the number $$$1235$$$ is part of the sequence $$$a$$$, but the numbers $$$4321$$$, $$$443$$$ are not part of the sequence $$$a$$$.

Bob realized that he does not know how to quickly search for a particular number by the position $$$k$$$ in the sequence, so he asks for your help.

For example, if Bob wants to find the number at position $$$k = 4$$$ (indexing from $$$1$$$), you need to answer $$$a_k = 5$$$.

## Input Format
The first line of input data contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

In the only line of each test case, there is a single integer $$$k$$$ ($$$1 \le k \le 10^{12}$$$) — the position Bob is interested in.

## Output Format
For each test case, print on a separate line the number $$$a_k$$$ in indexing with $$$1$$$.

## Examples
```input
7
3
5
22
10
100
12345
827264634912
```
```output
3
6
25
11
121
18937
2932285320890
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Vlad found a flowerbed with graphs in his yard and decided to take one for himself. Later he found out that in addition to the usual graphs, $$$k$$$-flowers also grew on that flowerbed. A graph is called a $$$k$$$-flower if it consists of a simple cycle of length $$$k$$$, through each vertex of which passes its own simple cycle of length $$$k$$$ and these cycles do not intersect at the vertices. For example, $$$3$$$-flower looks like this:

Note that $$$1$$$-flower and $$$2$$$-flower do not exist, since at least $$$3$$$ vertices are needed to form a cycle.

Vlad really liked the structure of the $$$k$$$-flowers and now he wants to find out if he was lucky to take one of them from the flowerbed.

## Input Format
The first line of input contains the single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the test.

The descriptions of the cases follow. An empty string is written before each case.

The first line of each case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le \min(2 \cdot 10^5, \frac{n \cdot (n-1)}{2})$$$) — the number of vertices and edges in the graph, respectively.

The next $$$m$$$ lines contain two integers each $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) — numbers of vertices connected by an edge. It is guaranteed that the graph does not contain multiple edges and self-loops.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$. It is also guaranteed for the sum of $$$m$$$ over all test cases.

## Output Format
Output $$$t$$$ lines, each of which is the answer to the corresponding test case. As an answer, output "YES" if Vlad's graph is a $$$k$$$-flower for some $$$k$$$, and "NO" otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).

## Examples
```input
5
9 12
1 2
3 1
2 3
1 6
4 1
6 4
3 8
3 5
5 8
9 7
2 9
7 2
8 12
1 2
3 1
2 3
1 6
4 1
6 4
3 8
3 5
5 8
8 7
2 8
7 2
4 3
1 2
4 2
3 1
6 8
6 3
6 4
5 3
5 2
3 2
3 1
2 1
2 4
5 7
2 4
2 5
3 4
3 5
4 1
4 5
1 5
```
```output
YES
NO
NO
NO
NO
```
-----
```input
4
2 1
1 2
8 9
1 2
8 4
8 2
6 4
6 5
4 7
3 2
3 7
2 5
9 12
2 9
2 8
6 9
6 8
6 5
6 1
9 8
9 3
9 1
8 3
8 7
5 7
3 3
1 2
1 3
2 3
```
```output
NO
NO
NO
NO
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 5.0 seconds
Memory limit: 256.0 MB

# Problem
This is an easy version of the problem, it differs from the hard one only by constraints on $$$n$$$ and $$$k$$$.

Vlad found a row of $$$n$$$ tiles and the integer $$$k$$$. The tiles are indexed from left to right and the $$$i$$$-th tile has the color $$$c_i$$$. After a little thought, he decided what to do with it.

You can start from any tile and jump to any number of tiles right, forming the path $$$p$$$. Let's call the path $$$p$$$ of length $$$m$$$ nice if:

- $$$p$$$ can be divided into blocks of length exactly $$$k$$$, that is, $$$m$$$ is divisible by $$$k$$$;
- $$$c_{p_1} = c_{p_2} = \ldots = c_{p_k}$$$;
- $$$c_{p_{k+1}} = c_{p_{k+2}} = \ldots = c_{p_{2k}}$$$;
- $$$\ldots$$$
- $$$c_{p_{m-k+1}} = c_{p_{m-k+2}} = \ldots = c_{p_{m}}$$$;

Your task is to find the number of nice paths of maximum length. Since this number may be too large, print it modulo $$$10^9 + 7$$$.

## Input Format
The first line of each test contains the integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the test.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 100$$$) — the number of tiles in a row and the length of the block.

The second line of each test case contains $$$n$$$ integers $$$c_1, c_2, c_3, \dots, c_n$$$ ($$$1 \le c_i \le n$$$) — tile colors.

It is guaranteed that the sum of $$$n^3$$$ over all test cases does not exceed $$$5 \cdot 10^6$$$.

## Output Format
Print $$$t$$$ numbers, each of which is the answer to the corresponding test case — the number of nice paths of maximum length modulo $$$10^9 + 7$$$.

## Examples
```input
5
5 2
1 2 3 4 5
7 2
1 3 1 3 3 1 3
11 4
1 1 1 1 1 1 1 1 1 1 1
5 2
1 1 2 2 2
5 1
1 2 3 4 5
```
```output
1
4
165
3
1
```

## Note
In the first sample, it is impossible to make a nice path with a length greater than $$$0$$$.

In the second sample, we are interested in the following paths:

- $$$1 \rightarrow 3 \rightarrow 4 \rightarrow 5$$$
- $$$2 \rightarrow 4 \rightarrow 5 \rightarrow 7$$$
- $$$1 \rightarrow 3 \rightarrow 5 \rightarrow 7$$$
- $$$1 \rightarrow 3 \rightarrow 4 \rightarrow 7$$$

In the third example, any path of length $$$8$$$ is nice.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
After holding one team contest, boy Yura got very tired and wanted to change his life and move to Japan. In honor of such a change, Yura changed his name to something nice.

Fascinated by this idea he already thought up a name $$$s$$$ consisting only of characters "_" and "^". But there's a problem — Yura likes smiley faces "^_^" and "^^". Therefore any character of the name must be a part of at least one such smiley. Note that only the consecutive characters of the name can be a smiley face.

More formally, consider all occurrences of the strings "^_^" and "^^" in the string $$$s$$$. Then all such occurrences must cover the whole string $$$s$$$, possibly with intersections. For example, in the string "^^__^_^^__^" the characters at positions $$$3,4,9,10$$$ and $$$11$$$ are not contained inside any smileys, and the other characters at positions $$$1,2,5,6,7$$$ and $$$8$$$ are contained inside smileys.

In one operation Jura can insert one of the characters "_" and "^" into his name $$$s$$$ (you can insert it at any position in the string). He asks you to tell him the minimum number of operations you need to do to make the name fit Yura's criteria.

## Input Format
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) —the number of test cases. The description of test cases follows.

The first and only line of each test case contains a single string $$$s$$$ ($$$1 \leq |s| \leq 100$$$), consisting of characters "_" and "^",  — the name to change.

## Output Format
For each test case, output a single integer — the minimum number of characters you need to add to the name to make it fit for Yura. If you don't need to change anything in the name, print $$$0$$$.

## Examples
```input
7
^______^
___^_^^^_^___^
^_
^
^_^^^^^_^_^^
___^^
_
```
```output
5
5
1
1
0
3
2
```

## Note
In the first test case, you can get the following name by adding $$$5$$$ characters:

^_^_^_^_^_^_^

In the third test case, we can add one character "^" to the end of the name, then we get the name:

^_^

In the fourth test case, we can add one character "^" to the end of the name, then we get the name:

^^

In the fifth test case, all of the characters are already contained in smiley faces, so the answer is $$$0$$$.

In the seventh test case, you can add one character "^" at the beginning of the name and one character "^" at the end of the name, then you get the name:

^_^

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array $$$a$$$ of $$$n$$$ integers, where all elements $$$a_i$$$ lie in the range $$$[1, k]$$$. How many different arrays $$$b$$$ of $$$m$$$ integers, where all elements $$$b_i$$$ lie in the range $$$[1, k]$$$, contain $$$a$$$ as a subsequence? Two arrays are considered different if they differ in at least one position.

A sequence $$$x$$$ is a subsequence of a sequence $$$y$$$ if $$$x$$$ can be obtained from $$$y$$$ by the deletion of several (possibly, zero or all) elements.

Since the answer may be large, print it modulo $$$10^9 + 7$$$.

## Input Format
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains three integers $$$n$$$, $$$m$$$, $$$k$$$ ($$$1 \le n \le 2\cdot 10^5$$$, $$$n \le m \le 10^9$$$, $$$1 \le k \le 10^9$$$) — the size of $$$a$$$, the size of $$$b$$$, and the maximum value allowed in the arrays, respectively.

The next line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots a_n$$$ ($$$1\le a_i \le k$$$) — the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

## Output Format
For each test case, output a single integer — the number of suitable arrays $$$b$$$, modulo $$$10^9+7$$$.

## Examples
```input
7
1 1000000 1
1
3 4 3
1 2 2
5 7 8
1 2 3 4 1
6 6 18
18 2 2 5 2 16
1 10 2
1
8 10 1234567
1 1 2 1 2 2 2 1
5 1000000000 1000000000
525785549 816356460 108064697 194447117 725595511
```
```output
1
9
1079
1
1023
906241579
232432822
```

## Note
For the first example, since $$$k=1$$$, there is only one array of size $$$m$$$ consisting of the integers $$$[1, k]$$$. This array ($$$[1, 1, \ldots, 1]$$$) contains the original array as a subsequence, so the answer is 1.

For the second example, the $$$9$$$ arrays are $$$[1, 1, 2, 2]$$$, $$$[1, 2, 1, 2]$$$, $$$[1, 2, 2, 1]$$$, $$$[1, 2, 2, 2]$$$, $$$[1, 2, 2, 3]$$$, $$$[1, 2, 3, 2]$$$, $$$[1, 3, 2, 2]$$$, $$$[2, 1, 2, 2]$$$, $$$[3, 1, 2, 2]$$$.

For the fourth example, since $$$m=n$$$, the only array of size $$$m$$$ that contains $$$a$$$ as a subsequence is $$$a$$$ itself.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Tenzing has $$$n$$$ balls arranged in a line. The color of the $$$i$$$-th ball from the left is $$$a_i$$$.

Tenzing can do the following operation any number of times:

- select $$$i$$$ and $$$j$$$ such that $$$1\leq i < j \leq |a|$$$ and $$$a_i=a_j$$$,
- remove $$$a_i,a_{i+1},\ldots,a_j$$$ from the array (and decrease the indices of all elements to the right of $$$a_j$$$ by $$$j-i+1$$$).

Tenzing wants to know the maximum number of balls he can remove.

## Input Format
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1\leq t\leq 10^3$$$) — the number of test cases. The description of test cases follows.

The first line contains a single integer $$$n$$$ ($$$1\leq n\leq 2\cdot 10^5$$$) — the number of balls.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\leq a_i \leq n$$$) — the color of the balls.

It is guaranteed that sum of $$$n$$$ of all test cases will not exceed $$$2\cdot 10^5$$$.

## Output Format
For each test case, output the maximum number of balls Tenzing can remove.

## Examples
```input
2
5
1 2 2 3 3
4
1 2 1 2
```
```output
4
3
```

## Note
In the first example, Tenzing will choose $$$i=2$$$ and $$$j=3$$$ in the first operation so that $$$a=[1,3,3]$$$. Then Tenzing will choose $$$i=2$$$ and $$$j=3$$$ again in the second operation so that $$$a=[1]$$$. So Tenzing can remove $$$4$$$ balls in total.

In the second example, Tenzing will choose $$$i=1$$$ and $$$j=3$$$ in the first and only operation so that $$$a=[2]$$$. So Tenzing can remove $$$3$$$ balls in total.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
Tenzing has an undirected tree of $$$n$$$ vertices.

Define the value of a tree with black and white vertices in the following way. The value of an edge is the absolute difference between the number of black nodes in the two components of the tree after deleting the edge. The value of the tree is the sum of values over all edges.

For all $$$k$$$ such that $$$0 \leq k \leq n$$$, Tenzing wants to know the maximum value of the tree when $$$k$$$ vertices are painted black and $$$n-k$$$ vertices are painted white.

## Input Format
The first line of the input contains a single integer $$$n$$$ ($$$1\leq n\leq 5000$$$) — the number of vertices.

The following $$$n-1$$$ lines of the input contains $$$2$$$ integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n, u_i \neq v_i$$$) — indicating an edge between vertices $$$u_i$$$ and $$$v_i$$$. It is guaranteed that the given edges form a tree.

## Output Format
Output $$$n+1$$$ numbers. The $$$i$$$-th number is the answer of $$$k=i-1$$$.

## Examples
```input
4
1 2
3 2
2 4
```
```output
0 3 4 5 6
```
-----
```input
1
```
```output
0 0
```

## Note
Consider the first example. When $$$k=2$$$, Tenzing can paint vertices $$$1$$$ and $$$2$$$ black then the value of edge $$$(1,2)$$$ is 0, and the values of other edges are all equal to $$$2$$$. So the value of that tree is $$$4$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 1024.0 MB

# Problem
Tenzing has an array $$$a$$$ of length $$$n$$$ and an integer $$$v$$$.

Tenzing will perform the following operation $$$m$$$ times:

1. Choose an integer $$$i$$$ such that $$$1 \leq i \leq n$$$ uniformly at random.
2. For all $$$j$$$ such that $$$i \leq j \leq n$$$, set $$$a_j := a_j + v$$$.

Tenzing wants to know the expected value of $$$\prod_{i=1}^n a_i$$$ after performing the $$$m$$$ operations, modulo $$$10^9+7$$$.

Formally, let $$$M = 10^9+7$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output the integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

## Input Format
The first line of input contains three integers $$$n$$$, $$$m$$$ and $$$v$$$ ($$$1\leq n\leq 5000$$$, $$$1\leq m,v\leq 10^9$$$).

The second line of input contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\leq a_i\leq 10^9$$$).

## Output Format
Output the expected value of $$$\prod_{i=1}^n a_i$$$ modulo $$$10^9+7$$$.

## Examples
```input
2 2 5
2 2
```
```output
84
```
-----
```input
5 7 9
9 9 8 2 4
```
```output
975544726
```

## Note
There are three types of $$$a$$$ after performing all the $$$m$$$ operations :

1. $$$a_1=2,a_2=12$$$ with $$$\frac{1}{4}$$$ probability.

2. $$$a_1=a_2=12$$$ with $$$\frac{1}{4}$$$ probability.

3. $$$a_1=7,a_2=12$$$ with $$$\frac{1}{2}$$$ probability.

So the expected value of $$$a_1\cdot a_2$$$ is $$$\frac{1}{4}\cdot (24+144) + \frac{1}{2}\cdot 84=84$$$.

Now solve the problem and return the code.