Problem Statement

You are given a string S of length 3N, containing exactly N letters A, N letters B, and N letters C.

Let's call a string T consisting of letters A, B, and C good, if the following conditions hold:

• The length of T is divisible by 3. Let's denote it by 3K.
• T_1 = T_2 = \ldots = T_K
• T_{K+1} = T_{K+2} = \ldots = T_{2K}
• T_{2K+1} = T_{2K+2} = \ldots = T_{3K}.
• Letters T_1, T_{K+1} and T_{2K+1} are different from each other.

Examples of good strings are ABC, BBAACC, and AAACCCBBB.

Find a way to split S into at most 6 (not necessarily contiguous) subsequences so that the letters from each subsequence form a good string.

It can be proved that, under the constraints of the problem, it's always possible.

Constraints

• 1 \le N \le 2\cdot 10^5
• The string S contains N letters A, N letters B, and N letters C.

Sample Input 1

2
ABCCBA

Sample Output 1

111222

S is split into subsequences ABC and CBA, and each of them is a good string.

Sample Input 2

4
AABCBCAACBCB

Sample Output 2

111211241244

Positions of 1 form a subsequence AABBCC, positions of 2 form a subsequence CAB, and positions of 4 form a subsequence ACB. All of these strings are good.

Problem Statement

You are given a string S of length N, consisting of A, B, and C. You are allowed to perform the following operation any number of times:

• Choose any i with 1 \le i \le N-2, such that S_iS_{i+1}S_{i+2} is equal to ABC, BCA, or CAB. Then, replace the three characters with ABC, BCA, or CAB.

For example, you can perform the following transformations with string AABC:

• AABC \to ABCA \to BCAA

Determine if you can obtain string T from string S with some finite (maybe zero) number of operations above.

Constraints

• 3\le N \le 5\cdot 10^5
• S is a string of length N consisting of A, B, and C.
• T is a string of length N consisting of A, B, and C.

Sample Input 1

4
AABC
BCAA

Sample Output 1

YES

This example was explained in the statement.

Sample Input 2

4
ABCA
BCAB

Sample Output 2

NO

Problem Statement

You are given integers N and M. Find the number of arrays A=[A_1, A_2, \ldots, A_N] of length N such that the following conditions hold:

• 2 \le A_i \le M (1 \leq i \leq N)
• There exists a permutation P=[P_1,P_2,\ldots,P_N] of integers from 1 to N with the following property:
  • For every i from 1 to N, A_i equals the length of the longest increasing subsequence of the sequence [P_1, P_2, \ldots, P_{i-1}, P_{i+1}, \ldots, P_{N-1}, P_N].

As this number can be very large, output it modulo some prime Q.

Constraints

• 3 \le N \le 5000.
• 2 \le M \le N-1.
• 10^8 \le Q \le 10^9
• Q is a prime.

Sample Input 1

3 2 686926217

Sample Output 1

1

The only such array is [2, 2, 2], for which exists a permutation [1, 2, 3].

Sample Input 2

4 3 354817471

Sample Output 2

9

There are 9 such arrays: [2, 2, 2, 2], [2, 2, 2, 3], [2, 2, 3, 2], [2, 2, 3, 3], [2, 3, 2, 2], [2, 3, 3, 2], [3, 2, 2, 2], [3, 3, 2, 2], [3, 3, 3, 3].

Sample Input 3

5 2 829412599

Sample Output 3

1

The only such array is [2, 2, 2, 2, 2].

Sample Input 4

5 3 975576997

Sample Output 4

23

Sample Input 5

69 42 925171057

Sample Output 5

801835311

Problem Statement

Let's call a string T of length 3N, containing exactly N letters A, N letters B, and N letters C, good, if it can be split into N (not necessarily contiguous) subsequences of length 3, so that the letters from each subsequence form ABC, BCA, or CAB.

You are given a string S of length 3N, consisting of characters A, B, C, and ?. Count the number of ways to replace each ? with one of A, B, and C, so that the resulting string is good. As this number can be very large, output it modulo 998244353.

Constraints

• 1\le N \le 15.
• S is a string of length 3N, consisting of A, B, C, and ?.

Sample Input 1

1
???

Sample Output 1

3

There are 3 good strings you can obtain: ABC, BCA, and CAB.

Sample Input 2

2
AA????

Sample Output 2

2

There are 2 good strings you can obtain: AABBCC and AABCBC.

Sample Input 3

3
?A?A?A?A?

Sample Output 3

0

It's impossible to obtain a good string, as there are already 4 A's.

Sample Input 4

9
?????????A??B??C???????????

Sample Output 4

331653164

Problem Statement

You have N sets S_1, S_2, \ldots, S_N. Initially, for each i from 1 to N, set S_i contains only integer i (that is, S_i = \{i\}).

You are allowed to perform the following operation:

• Choose any i with 1 \le i \le N-1. Let U = S_i \cup S_{i+1} ー the union of sets S_i and S_{i+1}. Then, replace both S_i and S_{i+1} with U.

You want to perform a finite number of operations above (maybe zero), to get a configuration, in which S_i = \{L_i, L_i+1, \ldots, R_i-1, R_i\} for all i from 1 to N. Is it possible to reach this configuration? If it is possible, also find the smallest number of operations needed to reach it.

Constraints

• 1 \le N \le 5\cdot 10^5
• 1 \le L_i \le R_i \le N

Sample Input 1

3
1 2
1 2
1 3

Sample Output 1

-1

It can be proved that it's impossible to obtain the required configuration.

Sample Input 2

4
1 3
1 4
1 4
2 4

Sample Output 2

4

We can perform the following sequence of operations:

• Choose i = 2, get S_1 = \{1\}, S_2 = \{2, 3\}, S_3 = \{2, 3\}, S_4 = \{4\}
• Choose i = 1, get S_1 = \{1, 2, 3\}, S_2 = \{1, 2, 3\}, S_3 = \{2, 3\}, S_4 = \{4\}
• Choose i = 3, get S_1 = \{1, 2, 3\}, S_2 = \{1, 2, 3\}, S_3 = \{2, 3, 4\}, S_4 = \{2, 3, 4\}
• Choose i = 2, get S_1 = \{1, 2, 3\}, S_2 = \{1, 2, 3, 4\}, S_3 = \{1, 2, 3, 4\}, S_4 = \{2, 3, 4\}

Problem Statement

You are given integers N and K.

Let's call an integer array a=[a_1, a_2, \ldots, a_K] of length K good, if 1 \le a_i \le i for all 1 \le i \le K.

Let's call an integer array b=[b_1, b_2, \ldots, b_{NK}] of length NK amazing, if it can be split into N (not necessarily contiguous) subsequences of length K, each of which is good.

Let's define f(pos, val) as the number of amazing sequences b such that b_{pos}=val.

Find f(pos, val) for all 1\le pos \le NK, 1 \le val \le K. As these numbers can be very big, output them modulo some prime P.

Constraints

• 1 \le N \le 20.
• 1 \le K \le 20.
• 10^8 \le P \le 10^9
• P is a prime.

Sample Input 1

2 2 965166677

Sample Output 1

6 0 
4 2 
4 2 
3 3 

There exist 6 amazing arrays:

• [1, 1, 1, 1] ー can be split into [b_1, b_2], [b_3, b_4].
• [1, 1, 1, 2] ー can be split into [b_1, b_2], [b_3, b_4].
• [1, 2, 1, 1] ー can be split into [b_1, b_2], [b_3, b_4].
• [1, 2, 1, 2] ー can be split into [b_1, b_2], [b_3, b_4].
• [1, 1, 2, 1] ー can be split into [b_1, b_3], [b_2, b_4].
• [1, 1, 2, 2] ー can be split into [b_1, b_3], [b_2, b_4].