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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given two integers $$$n$$$ and $$$m$$$ and an array $$$a$$$ of $$$n$$$ integers. For each $$$1 \le i \le n$$$ it holds that $$$1 \le a_i \le m$$$.

Your task is to count the number of different arrays $$$b$$$ of length $$$n$$$ such that:

- $$$1 \le b_i \le m$$$ for each $$$1 \le i \le n$$$, and
- $$$\gcd(b_1,b_2,b_3,...,b_i) = a_i$$$ for each $$$1 \le i \le n$$$.

Here $$$\gcd(a_1,a_2,\dots,a_i)$$$ denotes the greatest common divisor (GCD) of integers $$$a_1,a_2,\ldots,a_i$$$.

Since this number can be too large, print it modulo $$$998\,244\,353$$$.

## Input Format
Each test consist 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 line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 10^9$$$) — the length of the array $$$a$$$ and the maximum possible value of the element.

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

It is guaranteed that the sum of $$$n$$$ across all test cases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print a single integer — the number of different arrays satisfying the conditions above. Since this number can be large, print it modulo $$$998\,244\,353$$$.

## Examples
```input
5
3 5
4 2 1
2 1
1 1
5 50
2 3 5 2 3
4 1000000000
60 30 1 1
2 1000000000
1000000000 2
```
```output
3
1
0
595458194
200000000
```

## Note
In the first test case, the possible arrays $$$b$$$ are:

- $$$[4,2,1]$$$;
- $$$[4,2,3]$$$;
- $$$[4,2,5]$$$.

In the second test case, the only array satisfying the demands is $$$[1,1]$$$.

In the third test case, it can be proven no such array exists.

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
Everyone was happy coding, until suddenly a power shortage happened and the best competitive programming site went down. Fortunately, a system administrator bought some new equipment recently, including some UPSs. Thus there are some servers that are still online, but we need all of them to be working in order to keep the round rated.

Imagine the servers being a binary string $$$s$$$ of length $$$n$$$. If the $$$i$$$-th server is online, then $$$s_i = 1$$$, and $$$s_i = 0$$$ otherwise.

A system administrator can do the following operation called electricity spread, that consists of the following phases:

- Select two servers at positions $$$1 \le i < j \le n$$$ such that both are online (i.e. $$$s_i=s_j=1$$$). The spread starts only from online servers.
- Check if we have enough power to make the spread. We consider having enough power if the number of turned on servers in range $$$[i, j]$$$ is at least the number of turned off servers in range $$$[i, j]$$$. More formally, check whether $$$2 \cdot (s_i + s_{i+1} + \ldots + s_j) \ge j - i + 1$$$.
- If the check is positive, turn on all the offline servers in range $$$[i, j]$$$. More formally, make $$$s_k := 1$$$ for all $$$k$$$ from $$$i$$$ to $$$j$$$.

We call a binary string $$$s$$$ of length $$$n$$$ rated if we can turn on all servers (i.e. make $$$s_i = 1$$$ for $$$1 \le i \le n$$$) using the electricity spread operation any number of times (possibly, $$$0$$$). Your task is to find the number of rated strings of length $$$n$$$ modulo $$$m$$$.

## Input Format
The first and only line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 5000$$$, $$$10 \le m \le 10^9$$$) — the length of the string and the required module.

## Output Format
Print a single integer — the number of rated binary strings of length $$$n$$$. Since this number can be large, print it modulo $$$m$$$.

## Examples
```input
2 100
```
```output
1
```
-----
```input
3 10
```
```output
2
```
-----
```input
4 3271890
```
```output
4
```
-----
```input
17 123456
```
```output
32347
```

## Note
In the first example, the only rated string is 11. So the answer is $$$1$$$.

In the second example, the rated strings are:

- 111;
- 101, because we can perform an operation with $$$i = 1$$$ and $$$j = 3$$$.

In the third sample, the rated strings are:

- 1001;
- 1111;
- 1011;
- 1101.

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
You are given a binary string $$$s$$$ of length $$$n$$$. We define a maximal substring as a substring that cannot be extended while keeping all elements equal. For example, in the string $$$11000111$$$ there are three maximal substrings: $$$11$$$, $$$000$$$ and $$$111$$$.

In one operation, you can select two maximal adjacent substrings. Since they are maximal and adjacent, it's easy to see their elements must have different values. Let $$$a$$$ be the length of the sequence of ones and $$$b$$$ be the length of the sequence of zeros. Then do the following:

- If $$$a \ge b$$$, then replace $$$b$$$ selected zeros with $$$b$$$ ones.
- If $$$a < b$$$, then replace $$$a$$$ selected ones with $$$a$$$ zeros.

As an example, for $$$1110000$$$ we make it $$$0000000$$$, for $$$0011$$$ we make it $$$1111$$$. We call a string being good if it can be turned into $$$1111...1111$$$ using the aforementioned operation any number of times (possibly, zero). Find the number of good substrings among all $$$\frac{n(n+1)}{2}$$$ non-empty substrings of $$$s$$$.

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

The first line of each test case contains $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the string $$$s$$$.

The second line of each test case contains the binary string $$$s$$$ of length $$$n$$$.

It is guaranteed that sum of $$$n$$$ across all test cases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print a single integer — the number of good substrings.

## Examples
```input
4
6
100011
3
101
5
11111
6
010101
```
```output
8
5
15
18
```

## Note
Let's define a substring from index $$$l$$$ to index $$$r$$$ as $$$[l, r]$$$.

For the first test case, the good substrings are:

- $$$[1,1]$$$,
- $$$[1,2]$$$,
- $$$[3,6]$$$,
- $$$[4,5]$$$,
- $$$[4,6]$$$,
- $$$[5,5]$$$,
- $$$[5,6]$$$,
- $$$[6,6]$$$.

In the second test case, all substrings are good except $$$[2,2]$$$.

In the third test case, all substrings are good.

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
You work in the quality control department of technical support for a large company. Your job is to make sure all client issues have been resolved.

Today you need to check a copy of a dialog between a client and a technical support manager. According to the rules of work, each message of the client must be followed by one or several messages, which are the answer of a support manager. However, sometimes clients ask questions so quickly that some of the manager's answers to old questions appear after the client has asked some new questions.

Due to the privacy policy, the full text of messages is not available to you, only the order of messages is visible, as well as the type of each message: a customer question or a response from the technical support manager. It is guaranteed that the dialog begins with the question of the client.

You have to determine, if this dialog may correspond to the rules of work described above, or the rules are certainly breached.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). Description of the test cases follows.

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 100$$$) — the total number of messages in the dialog.

The second line of each test case consists of $$$n$$$ characters "Q" and "A", describing types of messages in the dialog in chronological order. Character "Q" denotes the message with client question, and character "A" — the message with technical support manager answer. It is guaranteed that the first character in the line equals to "Q".

## Output Format
For each test case print "Yes" (without quotes) if dialog may correspond to the rules of work, or "No" (without quotes) otherwise.

## Examples
```input
5
4
QQAA
4
QQAQ
3
QAA
1
Q
14
QAQQAQAAQQQAAA
```
```output
Yes
No
Yes
No
Yes
```

## Note
In the first test case the two questions from the client are followed with two specialist's answers. So this dialog may correspond to the rules of work.

In the second test case one of the first two questions was not answered.

In the third test case the technical support manager sent two messaged as the answer to the only message of the client.

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
You are given three integers $$$n$$$, $$$a$$$, and $$$b$$$. Determine if there exist two permutations $$$p$$$ and $$$q$$$ of length $$$n$$$, for which the following conditions hold:

- The length of the longest common prefix of $$$p$$$ and $$$q$$$ is $$$a$$$.
- The length of the longest common suffix of $$$p$$$ and $$$q$$$ is $$$b$$$.

A permutation of length $$$n$$$ is an array containing each integer from $$$1$$$ to $$$n$$$ exactly once. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

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

The only line of each test case contains three integers $$$n$$$, $$$a$$$, and $$$b$$$ ($$$1\leq a,b\leq n\leq 100$$$).

## Output Format
For each test case, if such a pair of permutations exists, output "Yes"; otherwise, output "No". You can output each letter in any case (upper or lower).

## Examples
```input
4
1 1 1
2 1 2
3 1 1
4 1 1
```
```output
Yes
No
No
Yes
```

## Note
In the first test case, $$$[1]$$$ and $$$[1]$$$ form a valid pair.

In the second test case and the third case, we can show that such a pair of permutations doesn't exist.

In the fourth test case, $$$[1,2,3,4]$$$ and $$$[1,3,2,4]$$$ form a valid pair.

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
Define a cyclic sequence of size $$$n$$$ as an array $$$s$$$ of length $$$n$$$, in which $$$s_n$$$ is adjacent to $$$s_1$$$.

Muxii has a ring represented by a cyclic sequence $$$a$$$ of size $$$n$$$.

However, the ring itself hates equal adjacent elements. So if two adjacent elements in the sequence are equal at any time, one of them will be erased immediately. The sequence doesn't contain equal adjacent elements initially.

Muxii can perform the following operation until the sequence becomes empty:

- Choose an element in $$$a$$$ and erase it.

For example, if ring is $$$[1, 2, 4, 2, 3, 2]$$$, and Muxii erases element $$$4$$$, then ring would erase one of the elements equal to $$$2$$$, and the ring will become $$$[1, 2, 3, 2]$$$.

Muxii wants to find the maximum number of operations he could perform.

Note that in a ring of size $$$1$$$, its only element isn't considered adjacent to itself (so it's not immediately erased).

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

The first line of each test case contains a single integer $$$n$$$ ($$$1\leq n\leq 100$$$) — the size of the cyclic sequence.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\leq a_i\leq n$$$) — the sequence itself.

It's guaranteed that $$$a_i\ne a_{i+1}$$$ for $$$1\leq i<n$$$.

It's guaranteed that $$$a_n\ne a_1$$$ when $$$n>1$$$.

## Output Format
For each test case, output a single integer — the maximum number of operations Muxii can perform.

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

## Note
In the first test case, you can erase the second element first, then erase the remaining elements one by one in any order. In total, you can perform the operation $$$4$$$ times. Note that if you erase the first element first, then the sequence will be turned into $$$[2,3,2]$$$ and then immediately become $$$[2,3]$$$.

In the second test case, you can erase the first element first, then the sequence becomes $$$[2,1]$$$. Then you can erase all remaining elements one by one in any order.

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
You are given a binary matrix $$$b$$$ (all elements of the matrix are $$$0$$$ or $$$1$$$) of $$$n$$$ rows and $$$n$$$ columns.

You need to construct a $$$n$$$ sets $$$A_1, A_2, \ldots, A_n$$$, for which the following conditions are satisfied:

- Each set is nonempty and consists of distinct integers between $$$1$$$ and $$$n$$$ inclusive.
- All sets are distinct.
- For all pairs $$$(i,j)$$$ satisfying $$$1\leq i, j\leq n$$$, $$$b_{i,j}=1$$$ if and only if $$$A_i\subsetneq A_j$$$. In other words, $$$b_{i, j}$$$ is $$$1$$$ if $$$A_i$$$ is a proper subset of $$$A_j$$$ and $$$0$$$ otherwise.

Set $$$X$$$ is a proper subset of set $$$Y$$$, if $$$X$$$ is a nonempty subset of $$$Y$$$, and $$$X \neq Y$$$.

It's guaranteed that for all test cases in this problem, such $$$n$$$ sets exist. Note that it doesn't mean that such $$$n$$$ sets exist for all possible inputs.

If there are multiple solutions, you can output any of them.

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

The first line contains a single integer $$$n$$$ ($$$1\le n\le 100$$$).

The following $$$n$$$ lines contain a binary matrix $$$b$$$, the $$$j$$$-th character of $$$i$$$-th line denotes $$$b_{i,j}$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.

It's guaranteed that for all test cases in this problem, such $$$n$$$ sets exist.

## Output Format
For each test case, output $$$n$$$ lines.

For the $$$i$$$-th line, first output $$$s_i$$$ $$$(1 \le s_i \le n)$$$  — the size of the set $$$A_i$$$. Then, output $$$s_i$$$ distinct integers from $$$1$$$ to $$$n$$$  — the elements of the set $$$A_i$$$.

If there are multiple solutions, you can output any of them.

It's guaranteed that for all test cases in this problem, such $$$n$$$ sets exist.

## Examples
```input
2
4
0001
1001
0001
0000
3
011
001
000
```
```output
3 1 2 3
2 1 3
2 2 4
4 1 2 3 4
1 1
2 1 2
3 1 2 3
```

## Note
In the first test case, we have $$$A_1 = \{1, 2, 3\}, A_2 = \{1, 3\}, A_3 = \{2, 4\}, A_4 = \{1, 2, 3, 4\}$$$. Sets $$$A_1, A_2, A_3$$$ are proper subsets of $$$A_4$$$, and also set $$$A_2$$$ is a proper subset of $$$A_1$$$. No other set is a proper subset of any other set.

In the second test case, we have $$$A_1 = \{1\}, A_2 = \{1, 2\}, A_3 = \{1, 2, 3\}$$$. $$$A_1$$$ is a proper subset of $$$A_2$$$ and $$$A_3$$$, and $$$A_2$$$ is a proper subset of $$$A_3$$$.

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
Let $$$f(x,y)$$$ be the number of carries of $$$x+y$$$ in binary (i. e. $$$f(x,y)=g(x)+g(y)-g(x+y)$$$, where $$$g(x)$$$ is the number of ones in the binary representation of $$$x$$$).

Given two integers $$$n$$$ and $$$k$$$, find the number of ordered pairs $$$(a,b)$$$ such that $$$0 \leq a,b < 2^n$$$, and $$$f(a,b)$$$ equals $$$k$$$. Note that for $$$a\ne b$$$, $$$(a,b)$$$ and $$$(b,a)$$$ are considered as two different pairs.

As this number may be large, output it modulo $$$10^9+7$$$.

## Input Format
The only line of each test contains two integers $$$n$$$ and $$$k$$$ ($$$0\leq k<n\leq 10^6$$$).

## Output Format
Output a single integer  — the answer modulo $$$10^9+7$$$.

## Examples
```input
3 1
```
```output
15
```
-----
```input
3 0
```
```output
27
```
-----
```input
998 244
```
```output
573035660
```

## Note
Here are some examples for understanding carries:

$$$$$$ \begin{aligned} &\begin{array}{r} 1_{\ \ }1_{\ \ }1\\ +\ _{1}1_{\ \ }0_{\ \ }0\\ \hline \ 1_{\ \ }0_{\ \ }1_{\ \ }1 \end{array} &\begin{array}{r} \ 1_{\ \ }0_{\ \ }1\\ +\ _{\ \ }0_{\ \ }0_{1}1\\ \hline \ 0_{\ \ }1_{\ \ }1_{\ \ }0 \end{array} & &\begin{array}{r} \ 1_{\ \ }0_{\ \ }1\\ +\ _{1}0_{1}1_{1}1\\ \hline \ 1_{\ \ }0_{\ \ }0_{\ \ }0 \end{array} \end{aligned} $$$$$$

So $$$f(7,4)=1$$$, $$$f(5,1)=1$$$ and $$$f(5,3)=3$$$.

In the first test case, all the pairs meeting the constraints are $$$(1,1),(1,5),(2,2),(2,3),(3,2),(4,4),(4,5),(4,6),(4,7),(5,1),(5,4),(5,6),(6,4),(6,5),(7,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: 256.0 MB

# Problem
This is the easy version of the problem. The only difference between the two versions is the constraint on $$$n$$$. You can make hacks only if all versions of the problem are solved.

Let's call an array $$$a$$$ of odd length $$$2m+1$$$ (with $$$m \ge 1$$$) bad, if element $$$a_{m+1}$$$ is equal to the median of this array. In other words, the array is bad if, after sorting it, the element at $$$m+1$$$-st position remains the same.

Let's call a permutation $$$p$$$ of integers from $$$1$$$ to $$$n$$$ anti-median, if every its subarray of odd length $$$\ge 3$$$ is not bad.

You are already given values of some elements of the permutation. Find the number of ways to set unknown values to obtain an anti-median permutation. As this number can be very large, find it modulo $$$10^9+7$$$.

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

The first line of each test case contains a single integer $$$n$$$ $$$(2 \le n \le 1000)$$$  — the length of the permutation.

The second line of each test case contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$, or $$$p_i = -1$$$)  — the elements of the permutation. If $$$p_i \neq -1$$$, it's given, else it's unknown. It's guaranteed that if for some $$$i \neq j$$$ holds $$$p_i \neq -1, p_j \neq -1$$$, then $$$p_i \neq p_j$$$.

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

## Output Format
For each test case, output a single integer  — the number of ways to set unknown values to obtain an anti-median permutation, modulo $$$10^9+7$$$.

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

## Note
In the first test case, both $$$[1, 2]$$$ and $$$[2, 1]$$$ are anti-median.

In the second test case, permutations $$$[1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]$$$ are anti-median. The remaining two permutations, $$$[1, 2, 3]$$$, $$$[3, 2, 1]$$$, are bad arrays on their own, as their median, $$$2$$$, is in their middle.

In the third test case, $$$[1, 2, 3, 4]$$$ isn't anti-median, as it contains bad subarray $$$[1, 2, 3]$$$.

In the fourth test case, the only anti-median array you can get is $$$[5, 6, 3, 4, 1, 2]$$$.

Now solve the problem and return the code.