Problem Statement

A string x consisting of lowercase English letters is said to be good if and only if the following condition is satisfied.

• Every (contiguous) substring of x whose length is 2 or greater satisfies the following:
  • no character occupies the majority of that substring.

For example, acbca is not good because c occupies the majority of the substring cbc.

You are given a string S of length N consisting of lowercase English letters and ?. You want to replace each ? with a lowercase English letter of your choice to make S a good string. Find the number of ways to make S a good string, modulo 998244353.

Constraints

• 2 \leq N \leq 5000
• S is a string of length N consisting of lowercase English letters and ?.

Sample Input 1

3
a?b

Sample Output 1

24

Every way other than aab and abb satisfies the condition.

Sample Input 2

3
a?a

Sample Output 2

0

Sample Input 3

20
ugsyakganihodnwmktgi

Sample Output 3

1

Sample Input 4

20
??a???h?m?y?ts???tl?

Sample Output 4

444225229

Problem Statement

We have a grid with N rows and M columns. You want to write an integer between 0 and 2^K-1 in each square in the grid to satisfy the following condition.

• Consider a path that starts at the top-left square, repeatedly moves right or down to an adjacent square, and ends at the bottom-right square. Such a path is said to be good if and only if the total \mathrm{XOR} of the integers written on the squares visited (including the starting and ending points) is 0.
• There is exactly one good path, which is the path represented by a string S. The path represented by the string S is a path that, for each i (1 \leq i \leq N+M-2), the i-th move is right if the i-th character of S is R and down if that character is D.

Determine whether there is a way to write integers that satisfies the condition.

For each input file, solve T test cases.

Constraints

• 1 \leq T \leq 100
• 2 \leq N,M \leq 30
• 1 \leq K \leq 30
• S is a string containing exactly N-1 Ds and M-1 Rs.
• All numbers in the input are integers.

Sample Input 1

4
2 2 1
RD
4 3 1
RDDDR
15 20 18
DDRRRRRRRDDDDRRDDRDRRRRDDRDRDDRRR
20 15 7
DRRDDDDDRDDDRRDDRRRDRRRDDDDDRRRDD

Sample Output 1

Yes
No
Yes
No

As an example, for the first case, you can make the grid as follows.

11
00

Problem Statement

Consider a permutation P=(P_1,P_2,\cdots,P_{2^N-1}) of (1,2,\cdots,2^N-1). P is said to be heaplike if and only if all of the following conditions are satisfied.

• P_i < P_{2i} (1 \leq i \leq 2^{N-1}-1)
• P_i < P_{2i+1} (1 \leq i \leq 2^{N-1}-1)

You are given integers A and B. Let U=2^A and V=2^{B+1}-1.

Find the probability, modulo 998244353, that P_U<P_V for a heaplike permutation chosen uniformly at random.

Constraints

• 2 \leq N \leq 5000
• 1 \leq A,B \leq N-1
• All numbers in the input are integers.

Sample Input 1

2 1 1

Sample Output 1

499122177

There are two heaplike permutations: P=(1,2,3),(1,3,2). The probability that P_2<P_3 is 1/2.

Sample Input 2

3 1 2

Sample Output 2

124780545

Sample Input 3

4 3 2

Sample Output 3

260479386

Sample Input 4

2022 12 25

Sample Output 4

741532295

Problem Statement

Find the number of pairs (P,Q)=((P_1,P_2,\cdots,P_N),(Q_1,Q_2,\cdots,Q_N)) of permutations of (1,2,\cdots,N) that satisfy the following condition, modulo 998244353.

• For every i (1 \leq i \leq N-1), one of the two conditions below holds.
  • P_i < P_{i+1} and Q_i < Q_{i+1}.
  • P_i > P_{i+1} and Q_i > Q_{i+1}.

Constraints

• 2 \leq N \leq 2 \times 10^5
• All numbers in the input are integers.

Sample Input 1

2

Sample Output 1

2

Two pairs, (P,Q)=((1,2),(1,2)) and (P,Q)=((2,1),(2,1)), satisfy the condition.

Sample Input 2

3

Sample Output 2

10

Sample Input 3

4

Sample Output 3

88

Sample Input 4

10

Sample Output 4

286574791

Problem Statement

In this problem, a permutation of (1,2,\cdots,N) is occasionally called just a permutation.

For a permutation a=(a_1,a_2,\cdots,a_N), let f(a) be the number of cycles in a. More accurately, the value of f(a) is defined as follows.

• Consider an undirected graph consisting of N vertices numbered 1 to N. For each 1 \leq i \leq N, add an edge connecting vertex i and vertex a_i. Then, let f(a) be the number of connected components in this graph.

You are given a permutation P=(P_1,P_2,\cdots,P_N) and an integer K. Determine whether there is a permutation x that satisfies the following condition, and construct one if it exists.

• Let y_i=P_{x_i} to define a permutation y.
• Then, f(x)+f(y)=K holds.

For each input file, solve T test cases.

Constraints

• 1 \leq T \leq 10^5
• 2 \leq N \leq 2 \times 10^5
• 2 \leq K \leq 2N
• (P_1,P_2,\cdots,P_N) is a permutation of (1,2,\cdots,N).
• In each input file, the sum of N does not exceed 2 \times 10^5.
• All numbers in the input are integers.

Sample Input 1

3
3 3
1 3 2
2 2
2 1
4 8
1 2 3 4

Sample Output 1

Yes
2 1 3
No
Yes
1 2 3 4

In the first case, letting x=(2,1,3) makes y=(3,1,2), satisfying f(x)+f(y)=2+1=3.

Problem Statement

You have a simple undirected graph. Each vertex in this graph has an integer interval written on it, and there are C_{i,j} vertices with the interval [i,j] (1 \leq i \leq j \leq N). There are no vertices with other intervals.

For any two vertices, there is an undirected edge between them if and only if the written intervals intersect. Here, an interval [a,b] and an interval [c,d] intersect if and only if \max(a,c) \leq \min(b,d).

Find the number of spanning trees of this graph, modulo 998244353. Here, all vertices are pairwise distinguishable.

Constraints

• 2 \leq N \leq 400
• 1 \leq C_{i,j} \leq 10^4
• All numbers in the input are integers.

Sample Input 1

2
1 2
1

Sample Output 1

8

Sample Input 2

3
1 1 1
1 1
1

Sample Output 2

99

Sample Input 3

4
8 3 8 10
1 5 3
1 6
4

Sample Output 3

971555314

Sample Input 4

10
2742 5611 1401 5439 5220 8571 4998 4194 7443 2492
2393 3201 9106 1649 2456 1984 7159 9679 7695
808 4600 2573 7771 5839 9504 4381 3223
5325 2564 456 5050 6963 913 9072
310 1521 9816 6205 2988 3614
4810 2979 2852 9242 6290
7551 7139 7228 699
4869 889 7597
4239 5970
865

Sample Output 4

234850531