Problem Statement

There is a chessboard with N rows and N columns. Let (i, j) denote the square at the i-th row from the top and the j-th column from the left.
You will now place pieces on the board. There are two types of pieces, called rooks and pawns.
A placement of pieces is called a good arrangement when it satisfies the following conditions:

• Each square has zero or one piece placed on it.
• If there is a rook at (i, j), there is no piece at (i, k) for all k (1 \leq k \leq N) where k \neq j.
• If there is a rook at (i, j), there is no piece at (k, j) for all k (1 \leq k \leq N) where k \neq i.
• If there is a pawn at (i, j) and i \geq 2, there is no piece at (i-1, j).

Is it possible to place all A rooks and B pawns on the board in a good arrangement?

You are given T test cases; solve each of them.

Constraints

• 1 \leq T \leq 10^5
• 1 \leq N \leq 10^4
• 0 \leq A, B
• 1 \leq A + B \leq N^2
• All input values are integers.

Sample Input 1

8
5 2 3
6 5 8
3 2 2
11 67 40
26 22 16
95 91 31
80 46 56
998 2 44353

Sample Output 1

Yes
No
No
No
Yes
No
Yes
Yes

In the first test case, for example, you can place rooks at (1, 1) and (2, 4), and pawns at (3, 3), (4, 2), and (5, 3) to have all the pieces in a good arrangement.
In the second test case, it is impossible to place all the pieces in a good arrangement.

Problem Statement

For a permutation P = (P_1, P_2, \dots, P_N) of (1, 2, \dots, N), we define F(P) by the following procedure:

• There is a sequence B = (1, 2, \dots, N).
  As long as there is an integer i such that B_i \lt P_{B_i}, perform the following operation:
  • Let j be the smallest integer i that satisfies B_i \lt P_{B_i}. Then, replace B_j with P_{B_j}.
  Define F(P) as the B at the end of this process. (It can be proved that the process terminates after a finite number of steps.)

You are given a sequence A = (A_1, A_2, \dots, A_N) of length N. How many permutations P of (1,2,\dots,N) satisfy F(P) = A? Find the count modulo 998244353.

Constraints

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

Sample Input 1

4
3 3 3 4

Sample Output 1

1

For example, if P = (2, 3, 1, 4), then F(P) is determined to be (3, 3, 3, 4) by the following steps:

• Initially, B = (1, 2, 3, 4).
• The smallest integer i such that B_i \lt P_{B_i} is 1. Replace B_1 with P_{B_1} = 2, making B = (2, 2, 3, 4).
• The smallest integer i such that B_i \lt P_{B_i} is 1. Replace B_1 with P_{B_1} = 3, making B = (3, 2, 3, 4).
• The smallest integer i such that B_i \lt P_{B_i} is 2. Replace B_2 with P_{B_2} = 3, making B = (3, 3, 3, 4).
• There are no more i that satisfy B_i \lt P_{B_i}, so the process ends. The current B = (3, 3, 3, 4) is defined as F(P).

There is only one permutation P such that F(P) = A, which is (2, 3, 1, 4).

Sample Input 2

4
2 2 4 3

Sample Output 2

0

Sample Input 3

8
6 6 8 4 5 6 8 8

Sample Output 3

18

Problem Statement

There is a tree with N vertices numbered 1 to N. The i-th edge connects vertices u_i and v_i.
Additionally, there are N pieces numbered 1 to N. Initially, piece i is placed on vertex i.
You can perform the following operation any number of times, possibly zero:

• Choose one edge. Let vertices u and v be the endpoints of the edge, and swap the pieces on vertices u and v. Then, delete the chosen edge.

Let a_i be the piece on vertex i. How many different possible sequences (a_1, a_2, \dots, a_N) exist when you finish performing the operation? Find the count modulo 998244353.

Constraints

• 2 \leq N \leq 3000
• 1 \leq u_i \lt v_i \leq N
• The graph given in the input is a tree.

Sample Input 1

3
1 2
2 3

Sample Output 1

5

For example, the sequence (a_1, a_2, a_3) = (2, 1, 3) can be obtained by the following steps:

• Choose the first edge, swap the pieces on vertices 1 and 2, and delete the edge. This results in (a_1, a_2, a_3) = (2, 1, 3).
• Finish operating.

Also, the sequence (a_1, a_2, a_3) = (3, 1, 2) can be obtained by the following steps:

• Choose the second edge, swap the pieces on vertices 2 and 3, and delete the edge. This results in (a_1, a_2, a_3) = (1, 3, 2).
• Choose the first edge, swap the pieces on vertices 1 and 2, and delete the edge. This results in (a_1, a_2, a_3) = (3, 1, 2).
• Finish operating.

The operation can yield the following five sequences:

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

Sample Input 2

5
2 5
3 4
1 3
1 5

Sample Output 2

34

Sample Input 3

8
4 5
2 5
3 6
1 3
1 8
2 7
2 8

Sample Output 3

799

Problem Statement

You are given non-negative integers P and B. Here, P is prime, and 1 \leq B \leq P-1.
For a sequence of non-negative integers X=(x_1,x_2,\dots,x_n), the hash value \mathrm{hash}(X) is defined as follows.

You are given M pairs of integers (L_1, R_1), (L_2, R_2), \dots, (L_M, R_M).
Is there a sequence of non-negative integers A=(A_1, A_2, \dots, A_N) of length N that satisfies the condition below?

• For all i (1 \leq i \leq M), the following condition holds:
  • Let s be the sequence (A_{L_i}, A_{L_i + 1}, \dots, A_{R_i}) obtained by taking the L_i-th to the R_i-th elements of A. Then, \mathrm{hash}(s) \neq 0.

Constraints

• 2 \leq P \leq 10^9
• P is prime.
• 1 \leq B \leq P - 1
• 1 \leq N \leq 16
• 1 \leq M \leq \frac{N(N+1)}{2}
• 1 \leq L_i \leq R_i \leq N
• (L_i, R_i) \neq (L_j, R_j) if i \neq j.
• All input values are integers.

Sample Input 1

3 2 3 3
1 1
1 2
2 3

Sample Output 1

Yes

The sequence A = (2, 0, 4) satisfies the condition because \mathrm{hash}((A_1)) = 2, \mathrm{hash}((A_1, A_2)) = 1, \mathrm{hash}((A_2, A_3)) = 1.

Sample Input 2

2 1 3 3
1 1
2 3
1 3

Sample Output 2

No

No sequence satisfies the condition.

Sample Input 3

998244353 986061415 6 11
1 5
2 2
2 5
2 6
3 4
3 5
3 6
4 4
4 5
4 6
5 6

Sample Output 3

Yes

Problem Statement

There is a grid with N rows and N columns. Let (i, j) denote the cell at the i-th row from the top and the j-th column from the left. Additionally, there is one black stone and M white stones.
You will play a single-player game using these items.

Here are the rules. Initially, you place the black stone at (A, B). Then, you place each of the M white stones on some cell of the grid. Here:

• You cannot place a white stone at (A, B).
• You can place at most one white stone per row.
• You can place at most one white stone per column.

Then, you will perform the following operation until you cannot do so:

• Assume the black stone is at (i, j). Perform one of the four operations below:
  • If there is a white stone at (i, k) where (j < k), remove that white stone and move the black stone to (i, k + 1).
  • If there is a white stone at (i, k) where (j > k), remove that white stone and move the black stone to (i, k - 1).
  • If there is a white stone at (k, j) where (i < k), remove that white stone and move the black stone to (k + 1, j).
  • If there is a white stone at (k, j) where (i > k), remove that white stone and move the black stone to (k - 1, j).
    • Here, if the cell to which the black stone is to be moved does not exist, such a move cannot be made.

The following figure illustrates an example. Here, B represents the black stone, W represents a white stone, . represents an empty cell, and O represents a cell to which the black stone can be moved.

..O...
..W...
......
......
..B.WO
......

You win the game if all of the following conditions are satisfied when you finish performing the operation. Otherwise, you lose.

• All white stones have been removed from the grid.
• The black stone is placed at (A, B).

In how many initial configurations of the M white stones can you win the game by optimally performing the operation? Find the count modulo 998244353.

Constraints

• 2 \leq M \leq N \leq 2 \times 10^5
• 1 \leq A \leq N
• 1 \leq B \leq N
• N, M, A, and B are integers.

Sample Input 1

6 4 2 3

Sample Output 1

4

For example, consider the white stones placed as shown in the following figure:

......
..BW..
.....W
......
..W...
....W.

Here, you can win the game by moving the black stone in the following steps:

• Remove the white stone at (5, 3) and move the black stone to (6, 3).
• Remove the white stone at (6, 5) and move the black stone to (6, 6).
• Remove the white stone at (3, 6) and move the black stone to (2, 6).
• Remove the white stone at (2, 4) and move the black stone to (2, 3).
• Since all white stones have been removed from the grid and the black stone is placed at (A, B) = (2, 3), you win the game.

There are four configurations of white stones that can lead to your victory.

Sample Input 2

5 3 1 3

Sample Output 2

0

Sample Input 3

200000 47718 21994 98917

Sample Output 3

146958602

Problem Statement

A string T is called a good string when it satisfies the following condition:

• There is a pair of strings (A, B) that satisfies all of the following:
  • Both A and B are non-empty.
  • A + B = T.
  • Both A + \mathrm{rev}(B) and \mathrm{rev}(A) + B are palindromes.

Here, A + B denotes the string formed by concatenating strings A and B in this order.
Also, \mathrm{rev}(A) denotes the string formed by reversing the order of the characters in string A.

There is a string S of length N consisting of lowercase English letters and the character ?.
Among the 26^{(\text{number of ?s})} ways to replace the ?s in S with lowercase English letters, how many result in a good string? Find the count modulo 998244353.

Constraints

• 2 \leq N \leq 5 \times 10^4
• S is a string of length N consisting of lowercase English letters and ?.

Sample Input 1

4
?ba?

Sample Output 1

1

The string abab is good, because if we set A = ab and B = ab, then A + B = abab, and both A + \mathrm{rev}(B) = abba and \mathrm{rev}(A) + B = baab are palindromes.
Among the strings that can be formed by replacing the ?s in S with lowercase English letters, there is only one good string, which is abab.

Sample Input 2

10
?y?x?x????

Sample Output 2

676

Sample Input 3

30
???a?????aab?a???c????c?aab???

Sample Output 3

193994800

Sample Input 4

36
????????????????????????????????????

Sample Output 4

363594614