Problem Statement

There are two persons, numbered 0 and 1, and a variable x whose initial value is 0. The two persons now play a game. The game is played in N rounds. The following should be done in the i-th round (1 \leq i \leq N):

• Person S_i does one of the following:
  • Replace x with x \oplus A_i, where \oplus represents bitwise XOR.
  • Do nothing.

Person 0 aims to have x=0 at the end of the game, while Person 1 aims to have x \neq 0 at the end of the game.

Determine whether x becomes 0 at the end of the game when the two persons play optimally.

Solve T test cases for each input file.

Constraints

• 1 \leq T \leq 100
• 1 \leq N \leq 200
• 1 \leq A_i \leq 10^{18}
• S is a string of length N consisting of 0 and 1.
• All numbers in input are integers.

Sample Input 1

3
2
1 2
10
2
1 1
10
6
2 3 4 5 6 7
111000

Sample Output 1

1
0
0

In the first test case, if Person 1 replaces x with 0 \oplus 1=1, we surely have x \neq 0 at the end of the game, regardless of the choice of Person 0.

In the second test case, regardless of the choice of Person 1, Person 0 can make x=0 with a suitable choice.

Problem Statement

Given is a string S, where each character is 0, 1, or ?.

Consider making a string S' by replacing each occurrence of ? with 0 or 1 (we can choose the character for each ? independently). Let us define the unbalancedness of S' as follows:

• (The unbalancedness of S') = \max \{ The absolute difference between the number of occurrences of 0 and 1 between the l-th and r-th character of S (inclusive) :\ 1 \leq l \leq r \leq |S|\}

Find the minimum possible unbalancedness of S'.

Constraints

• 1 \leq |S| \leq 10^6
• Each character of S is 0, 1, or ?.

Sample Input 1

0??

Sample Output 1

1

We can make S'= 010 and achieve the minimum possible unbalancedness of 1.

Sample Input 2

0??0

Sample Output 2

2

Sample Input 3

??00????0??0????0?0??00??1???11?1?1???1?11?111???1

Sample Output 3

4

Problem Statement

Snuke has a string x of length N. Initially, every character in x is 0.

Snuke can do the following two operations any number of times in any order:

• Choose A consecutive characters in x and replace each of them with 0.
• Choose B consecutive characters in x and replace each of them with 1.

Find the number of different strings that x can be after Snuke finishes doing operations. This count can be enormous, so compute it modulo (10^9+7).

Constraints

• 1 \leq N \leq 5000
• 1 \leq A,B \leq N
• All values in input are integers.

Sample Input 1

4 2 3

Sample Output 1

11

For example, x can be 0011 or 1111 in the end, but cannot be 0110.

Sample Input 2

10 7 2

Sample Output 2

533

Sample Input 3

1000 100 10

Sample Output 3

828178524

Problem Statement

We have N lamps numbered 1 to N, and N buttons numbered 1 to N. Initially, Lamp 1, 2, \cdots, A are on, and the other lamps are off.

Snuke and Ringo will play the following game.

• First, Ringo generates a permutation (p_1,p_2,\cdots,p_N) of (1,2,\cdots,N). The permutation is chosen from all N! possible permutations with equal probability, without being informed to Snuke.

• Then, Snuke does the following operation any number of times he likes:

  • Choose a lamp that is on at the moment. (The operation cannot be done if there is no such lamp.) Let Lamp i be the chosen lamp. Press Button i, which switches the state of Lamp p_i. That is, Lamp p_i will be turned off if it is on, and vice versa.

At every moment, Snuke knows which lamps are on. Snuke wins if all the lamps are on, and he will surrender when it turns out that he cannot win. What is the probability of winning when Snuke plays optimally?

Let w be the probability of winning. Then, w \times N! will be an integer. Compute w \times N! modulo (10^9+7).

Constraints

• 2 \leq N \leq 10^7
• 1 \leq A \leq \min(N-1,5000)

Sample Input 1

3 1

Sample Output 1

2

First, Snuke will press Button 1. If Lamp 1 turns off, he loses. Otherwise, he will press the button that he can now press. If the remaining lamp turns on, he wins; if Lamp 1 turns off, he loses. The probability of winning in this game is 1/3, so we should print (1/3)\times 3!=2.

Sample Input 2

3 2

Sample Output 2

3

Sample Input 3

8 4

Sample Output 3

16776

Sample Input 4

9999999 4999

Sample Output 4

90395416

Problem Statement

We have N boxes numbered 1 to N, and M balls numbered 1 to M. Currently, Ball i is in Box A_i.

You can do the following operation:

• Choose a box containing two or more balls, pick up one of the balls from that box, and put it into another box.

Since the balls are very easy to break, you cannot move Ball i more than C_i times in total. Within this limit, you can do the operation any number of times.

Your objective is to have Ball i in Box B_i for every i (1 \leq i \leq M). Determine whether this objective is achievable. If it is, also find the minimum number of operations required to achieve it.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq A_i,B_i \leq N
• 1 \leq C_i \leq 10^5
• In the situation where the objective is achieved, every box contains one or more balls. That is, for every i (1 \leq i \leq N), there exists j such that B_j=i.

Sample Input 1

3 3
1 2 1
2 1 1
1 3 2

Sample Output 1

3

We can achieve the objective in three operations, as follows:

• Pick up Ball 1 from Box 1 and put it into Box 2.
• Pick up Ball 2 from Box 2 and put it into Box 1.
• Pick up Ball 3 from Box 1 and put it into Box 3.

Sample Input 2

2 2
1 2 1
2 1 1

Sample Output 2

-1

Sample Input 3

5 5
1 2 1
2 1 1
1 3 2
4 5 1
5 4 1

Sample Output 3

6

Sample Input 4

1 1
1 1 1

Sample Output 4

0

Problem Statement

Snuke has X+Y balls. X of them have an integer A written on them, and the other Y of them have an integer B written on them.

Snuke will divide these balls into some number of groups. Here, every ball should be contained in exactly one group, and every group should contain one or more balls.

A group is said to be good when the sum of the integers written on the balls in that group is a multiple of an integer C. Find the maximum possible number of good groups.

Solve T test cases for each input file.

Constraints

• 1 \leq T \leq 2 \times 10^4
• 1 \leq A,X,B,Y,C \leq 10^9
• A \neq B

Sample Input 1

3
3 3 4 4 5
2 1 1 5 3
3 1 4 2 5

Sample Output 1

2
2
0

In the first test case, we can have two good groups by making the following groups: \{3,3,4\} and \{3,4,4,4\}.

In the second test case, we can have two good groups by making the following groups: \{2,1\}, \{1,1,1\}, and \{1\}.