Problem Statement

There are N people, numbered from 1 to N, who participated in a round-trip race between two points. The following information is recorded about this race.

• The outward times of any two people were different, and person i (1 \leq i \leq N) had the i-th fastest outward time.
• The round-trip times (the sum of the outward and return times) of any two people were different, and person i (1 \leq i \leq N) had the P_i-th fastest round-trip time.
• The person (or persons) with the fastest return time was awarded the fastest return award.

Here, P_1, P_2, \dots, P_N is a permutation of 1, 2, \dots, N.

How many people could have received the fastest return award?

There are T test cases. Answer each of them.

Constraints

• 1 \leq T \leq 500
• 2 \leq N \leq 10^3
• P_1, P_2, \dots, P_N is a permutation of 1, 2, \dots, N.
• All input values are integers.
• The sum of N over all test cases in a single input is at most 10^3.

Sample Input 1

3
2
2 1
4
1 2 3 4
20
13 2 7 1 5 9 3 4 12 10 15 6 8 14 20 16 19 18 11 17

Sample Output 1

1
4
7

• In the first test case, two people participated in the race, and person 2 overtook person 1 on the return leg. In this case, the fastest return award is awarded to person 2.
• In the second test case, the rankings did not change on the return leg, so any person could have received the fastest return award.

Problem Statement

A permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) is given.

Determine whether it is possible to rearrange P in ascending order by performing the following operation at most 2\times 10^3 times, and if possible, show one such sequence of operations.

• Choose integers i and j such that 1\leq i \leq N-1,0 \leq j \leq N-2. Let Q = (Q_1, Q_2,\ldots,Q_{N-2}) be the sequence obtained by removing (P_i,P_{i+1}) from P. Replace P with (Q_1,\ldots,Q_j, P_i, P_{i+1}, Q_{j+1},\ldots,Q_{N-2}).

Constraints

• 2 \leq N \leq 10^3
• P is a permutation of (1,2,\ldots,N).
• All input values are integers.

Sample Input 1

5
1 4 2 3 5

Sample Output 1

Yes
1
3 1

Perform the operation with i=3,j=1.

Then, Q=(P_1,P_2,P_5)=(1,4,5), so you get P=(Q_1,P_3,P_4,Q_2,Q_3) = (1,2,3,4,5).

Thus, P can be rearranged in ascending order with one operation.

Sample Input 2

2
2 1

Sample Output 2

No

It can be proved that P cannot be rearranged in ascending order within 2\times 10^3 operations.

Sample Input 3

4
3 4 1 2

Sample Output 3

Yes
3
3 0
1 2
3 0

There is no need to minimize the number of operations.

Problem Statement

You are given a rooted tree with N vertices numbered 1 to N. Vertex 1 is the root, and the parent of vertex i\ (2\leq i \leq N) is P_i.

Some vertices of the rooted tree have non-negative integers from 0 to N written on them. This information is given by the sequence A=(A_1,A_2,\ldots,A_N). If A_i \neq -1, vertex i has the integer A_i written on it; if A_i=-1, vertex i does not have an integer written on it.

Alice and Bob play a game. Alice goes first, and they take turns performing the following operation until all vertices have an integer written on them.

• Choose one vertex without an integer written on it and write a non-negative integer between 0 and N on it.

After the operations, for each vertex v, let f(v) be the smallest non-negative integer not written on any vertex (including v) in the subtree rooted at vertex v.

If there is a vertex v such that f(v) = K, Alice wins. Otherwise, Bob wins. Determine the winner when both players play optimally.

There are T test cases. Answer each of them.

Constraints

• 1 \leq T \leq 10^3
• 2 \leq N \leq 10^3
• 0 \leq K \leq N
• 1 \leq P_i < i\ (2\leq i\leq N)
• -1 \leq A_i \leq N\ (1\leq i\leq N)
• All input values are integers.
• The sum of N over all test cases in a single input is at most 2\times 10^3.

Sample Input 1

2
4 2
1 1 2
-1 -1 3 1
6 4
1 2 2 1 3
-1 -1 -1 -1 -1 -1

Sample Output 1

Alice
Bob

In the first test case, if Alice writes 0 on vertex 2, then f(2) = 2 regardless of Bob's operation. Therefore, Alice can win.

In the second test case, Bob can ensure that there will be no vertex with f(v) = 4 by choosing the right integer to write.

Problem Statement

In this problem, a rooted directed tree is a rooted tree where all edges are directed from the root to the leaves.

You are given a sequence of non-negative integers d=(d_1,d_2,\ldots,d_N) with a sum of N-1.

Among the N-vertex rooted directed trees with vertex numbered 1 to N and vertex 1 as the root, a good tree is one that satisfies the following condition:

• the out-degree of vertex i\ (1\leq i \leq N) is d_i.

Furthermore, for a vertex v of a good tree, let f(v) be the minimum vertex number of the vertices (including v) in the subtree rooted at vertex v, and v is called a good vertex if it satisfies f(v)=v.

Find the sum of the numbers of good vertices for all good trees, modulo 998244353.

Constraints

• 2 \leq N \leq 500
• 0 \leq d_i \leq N-1
• d_1 \geq 1
• \sum_{i=1}^N d_i = N-1
• All input values are integers.

Sample Input 1

4
2 0 1 0

Sample Output 1

7

There are two good trees, as shown below. The blue vertices are good vertices.

For these trees, there are 4 and 3 good vertices, respectively, so the answer is 7.

Sample Input 2

10
3 1 0 0 2 0 1 2 0 0

Sample Output 2

37542

Problem Statement

You are given a sequence of length N consisting of integers from 1 to N, A=(A_1,A_2,\ldots,A_N).

Find the number, modulo 998244353, of sequences of length N consisting of integers from 1 to N, B=(B_1,B_2,\ldots,B_N), that satisfy the following conditions for all i=1,2,\ldots,N.

• The number of occurrences of i in B is at most A_i.
• The number of occurrences of B_i in B is at most A_i.

Constraints

• 1 \leq N \leq 500
• 1 \leq A_i \leq N
• All input values are integers.

Sample Input 1

3
1 2 3

Sample Output 1

10

The following 10 sequences satisfy the conditions:

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

Sample Input 2

4
4 4 4 4

Sample Output 2

256

All sequences of length 4 consisting of integers from 1 to 4 satisfy the conditions, and there are 4^4=256 such sequences.

Sample Input 3

5
1 1 1 1 1

Sample Output 3

120

All permutations of (1,2,3,4,5) satisfy the conditions, and there are 5!=120 such sequences.

Sample Input 4

14
6 5 14 3 6 7 3 11 11 2 3 7 8 10

Sample Output 4

628377683

Be sure to print the number modulo 998244353.

Problem Statement

You are given positive integers N and M. Among the 2^{NM} matrices A with N rows and M columns where each element is 0 or 1, find the number, modulo 998244353, of ones that satisfy the following condition:

• A_{a, b} \times A_{c, d} \leq A_{a, d} \times A_{c, b} for every quadruple of integers (a, b, c, d) such that 1 \leq a < c \leq N and 1 \leq b < d \leq M.

Constraints

• 1 \leq N, M \leq 400
• All input values are integers.

Sample Input 1

2 2

Sample Output 1

13

The condition is A_{1,1} \times A_{2,2} \leq A_{1,2} \times A_{2,1}. All 13 matrices other than \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} satisfy the condition.

Sample Input 2

1 30

Sample Output 2

75497471

All 2^{NM} matrices satisfy the condition, so print 2^{30} modulo 998244353, that is, 75497471.

Sample Input 3

400 400

Sample Output 3

412670892