Problem Statement

For two N \times N matrices A and B whose elements are 0 or 1, we say that A and B are similar if they satisfy the following conditions:

• The sums of corresponding rows are equal. That is, A_{i,1} + \dots + A_{i,N} = B_{i,1} + \dots + B_{i,N} for any i=1,\dots,N.
• The sums of corresponding columns are equal. That is, A_{1,j} + \dots + A_{N,j} = B_{1,j} + \dots + B_{N,j} for any j=1,\dots,N.

Furthermore, for an N \times N matrix A whose elements are 0 or 1, and integers i,j (1 \leq i,j \leq N), we say that the element at row i column j is fixed if A_{i,j} = B_{i,j} holds for any matrix B that is similar to A.

Answer the following Q queries:

• The i-th query: If there exists an N \times N matrix whose elements are 0 or 1 such that exactly K_i elements are fixed, output Yes; otherwise, output No.

Constraints

• 2 \le N \le 30
• 1 \le Q \le N^2+1
• 0 \le K_i \le N^2
• K_i \ne K_j (1 \le i < j \le Q)
• All inputs are integers

Sample Input 1

3 3
0
9
7

Sample Output 1

Yes
Yes
No

Query 1: For example, the following matrix X has exactly 0 fixed elements.

1 0 0
0 1 0
0 0 1

This is because all the following matrices, obtained by cyclically shifting the columns, are similar to X, and each element can be either 0 or 1.

0 0 1
1 0 0
0 1 0

0 1 0
0 0 1
1 0 0

Query 2: For example, the following matrix X has exactly 9 fixed elements.

0 0 1
0 1 1
1 1 1

This is because no other matrix similar to X exists, and all elements are fixed.

Query 3: No matrix exists with exactly 7 fixed elements.

Sample Input 2

29 6
186
681
18
108
123
321

Sample Output 2

No
Yes
No
Yes
No
Yes

Problem Statement

You are given a sequence of integers (A_1,\dots,A_N) of length N. This sequence satisfies 0\le A_i < i for each i=1,\dots,N. Find the number of permutations (P_1,\dots,P_N) of (1,\dots,N) that satisfy the following conditions, modulo 998244353.

• For each i=1,\dots,N:
  • P_j > P_i for any integer j with A_i < j < i
  • P_{A_i} < P_i if A_i > 0

For the sequence (A_1,\dots,A_N) given in the input, it is guaranteed that there exists a permutation satisfying the conditions.

Constraints

• 1\le N\le 3\times 10^5
• 0\le A_i \lt i
• For A_1,\dots,A_N, there exists a permutation satisfying the conditions in the problem statement.
• All input values are integers.

Sample Input 1

4
0 1 0 3

Sample Output 1

3

There are three such permutations: (2, 3, 1, 4), (2, 4, 1, 3), and (3, 4, 1, 2).

Sample Input 2

22
0 1 2 2 2 2 2 2 1 9 9 9 9 0 14 15 15 15 14 19 19 19

Sample Output 2

353820794

The answer is 353820794, which is 2350309500 modulo 998244353.

Problem Statement

Mr. Ball and Mr. Box will play a game with balls and boxes.

Initially, Mr. Ball has 10^{100} balls of each of M different types, and Mr. Box has 10^{100} yen. There are N boxes, where the i-th box has capacity V_i and costs P_i yen. During the game, Mr. Box can buy any box at any time.

In this game, the following operations are repeated until the game ends:

1. Mr. Ball chooses one ball and gives it to Mr. Box.
2. Mr. Box either accepts the ball or ends the game without accepting it.
3. If Mr. Box accepts the ball, he chooses one of his purchased boxes and puts the ball in it.
4. If the box with the ball satisfies the following conditions, Mr. Box receives 1 yen. Otherwise, the game ends.
   • The number of balls in the box does not exceed its capacity.
   • All balls in the box are of the same type.

Mr. Ball will play optimally to minimize Mr. Box's final money, while Mr. Box will play optimally to maximize it. How much will Mr. Box's money increase throughout the game?

Here, both players have access to all information. In particular, Mr. Ball can see the capacity, price, and contents (type and number of balls) of each box. Also, note that Mr. Box's initial money is large enough that he will never run out of money to buy boxes.

Solve T test cases for each input file.

Constraints

• 1\le T,N,M\le 3\times 10^5
• 1\le V_i,P_i \le 10^9
• The sum of N over the T test cases is at most 3\times 10^5.
• All input values are integers.

Sample Input 1

3
3 2
1 1000000000
3 1
3 1
1 300000
1000000000 1
10 4
22 5
26 45
72 21
47 39
97 2
75 35
82 24
17 46
32 22
28 67

Sample Output 1

2
0
28

In the first test case, there are two types of balls and three boxes. Let us call the two types of balls white and black balls, and call the i-th box box i. Here is an example of how the game could proceed where the money increases by 2 yen.

1. Mr. Ball chooses and gives a white ball.
2. Mr. Box accepts the ball, buys box 2 for 1 yen, and puts the white ball in it.
   • Box 2 contains 1 white ball. This satisfies the conditions, so Mr. Box receives 1 yen.
3. Mr. Ball chooses and gives a white ball.
4. Mr. Box accepts the ball and puts it in box 2.
   • Box 2 contains 2 white balls. This satisfies the conditions, so Mr. Box receives 1 yen.
5. Mr. Ball chooses and gives a black ball.
6. Mr. Box accepts the ball, buys box 3 for 1 yen, and puts the black ball in it.
   • Box 3 contains 1 black ball. This satisfies the conditions, so Mr. Box receives 1 yen.
7. Mr. Ball chooses and gives a white ball.
8. Mr. Box accepts the ball and puts it in box 2.
   • Box 2 contains 3 white balls. This satisfies the conditions, so Mr. Box receives 1 yen.
9. Mr. Ball chooses and gives a white ball.
10. Mr. Box chooses to end the game without accepting it.

Finally, box 2 contains 3 white balls and box 3 contains 1 black ball. Mr. Box spent 2 yen and received 4 yen, so his money increased by 2 yen.

In the second test case, Mr. Ball can play in a way that prevents Mr. Box from earning any money.

Problem Statement

Whether a non-empty sequence of non-negative integers (V_1, V_2, \dots, V_M) is Polish or not is recursively defined as follows:

• We say (V_1, V_2, \dots, V_M) is Polish if there exist V_1 Polish sequences W_1, W_2, \dots, W_{V_1} such that the concatenation of sequences (V_1), W_1, W_2, \dots, W_{V_1} in this order equals (V_1, V_2, \dots, V_M).

In particular, the sequence (0) is Polish.

Given a sequence of non-negative integers (A_1, A_2, \dots, A_N) of length N, find the number of Polish sequences of length N that are lexicographically not greater than (A_1, A_2, \dots, A_N), modulo 998244353.

Constraints

• 1\leq N \leq 3\times 10^5
• 0\leq A_i \lt N
• All input values are integers.

Sample Input 1

6
1 1 1 2 0 0

Sample Output 1

2

(1, 1, 1, 1, 1, 0) and (1, 1, 1, 2, 0, 0) satisfy the conditions.

We can verify that (1, 1, 1, 2, 0, 0) is Polish as follows.

• As stated in the problem statement, (0) is Polish.
• (2, 0, 0) is Polish because it equals the concatenation of (2) and two Polish sequences (0) and (0) in this order.
• (1, 2, 0, 0) is Polish because it equals the concatenation of (1) and one Polish sequence (2, 0, 0) in this order.
• (1, 1, 2, 0, 0) is Polish because it equals the concatenation of (1) and one Polish sequence (1, 2, 0, 0) in this order.
• (1, 1, 1, 2, 0, 0) is Polish because it equals the concatenation of (1) and one Polish sequence (1, 1, 2, 0, 0) in this order.

Sample Input 2

11
3 3 4 4 5 5 6 6 7 7 8

Sample Output 2

13002

Sample Input 3

19
18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18

Sample Output 3

477638700

Sample Input 4

4
1 1 0 0

Sample Output 4

0

Problem Statement

You are given a sequence of integers (X_1,\dots,X_M) of length M consisting of 1,\dots,K.

Find the number of sequences (A_1,\dots,A_N) of length N consisting of 1,\dots,K that satisfy the following condition, modulo 998244353:

• Among all sequences of length M consisting of 1,\dots,K, the only sequence that cannot be obtained as a (not necessarily contiguous) subsequence of (A_1,\dots,A_N) is (X_1,\dots,X_M).

Constraints

• 2\le M,K \le N \le 400
• 1\le X_i \le K
• All input values are integers.

Sample Input 1

5 2 3
1 1

Sample Output 1

4

The following four sequences satisfy the condition:

• (2, 3, 1, 2, 3)
• (2, 3, 1, 3, 2)
• (3, 2, 1, 2, 3)
• (3, 2, 1, 3, 2)

Sample Input 2

400 3 9
1 8 6

Sample Output 2

417833302

Sample Input 3

29 3 10
3 3 3

Sample Output 3

495293602

Sample Input 4

29 3 10
3 3 4

Sample Output 4

0