Problem Statement

For a string T consisting of lowercase English letters, consider the question below, and let f(T) be the answer.

Find the number of different strings obtained by performing the following operation any number of times: delete the first character from T and append it to the end.

You are given a string S of length N consisting of lowercase English letters. You can perform the operation below at most K times (possibly zero).

• Choose a character of S and change it to any lowercase English letter.

Find the minimum possible value of f(S) after your operations.

Constraints

• 1 \le N \le 2000
• 0 \le K \le N
• S is a string of length N consisting of lowercase English letters.
• N and K are integers.

Sample Input 1

4 1
abac

Sample Output 1

2

If you change the fourth character c to b in the first operation, you get S= abab, with f(S)=2.

f(S) cannot be made 1 or less in one or fewer operations, so the answer is 2.

Sample Input 2

10 0
aaaaaaaaaa

Sample Output 2

1

Sample Input 3

6 1
abcaba

Sample Output 3

3

Problem Statement

You are given a string S of length N consisting of A,R,C.

As long as S contains three consecutive characters that are ARC, you can perform the operation below.

• In an odd-numbered (1-st, 3-rd, 5-th, ...) operation, choose in S three consecutive characters that are ARC, and replace them with R.
• In an even-numbered (2-nd, 4-th, 6-th, ...) operation, choose in S three consecutive characters that are ARC, and replace them with AC.

Find the maximum number of operations that can be performed.

Constraints

• 1 \leq N \leq 2\times 10^5
• S is a string of length N consisting of A,R,C.

Sample Input 1

6
AARCCC

Sample Output 1

2

You can perform two operations as follows.

AARCCC → ARCC → ACC

Sample Input 2

5
AAAAA

Sample Output 2

0

S does not contain three consecutive characters that are ARC, so you cannot perform the operation at all.

Sample Input 3

9
ARCARCARC

Sample Output 3

3

Problem Statement

The happiness of a permutation P=(P_1,P_2,\ldots,P_N) of (1,\dots,N) is defined as follows.

• Let A=(A_1,A_2,\ldots,A_{N-1}) be a sequence of length N-1 with A_i = |P_i-P_{i+1}|(1\leq i \leq N-1). The happiness of P is the length of a longest strictly increasing subsequence of A.

Print a permutation P such that P_1 = X with the greatest happiness.

Constraints

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

Sample Input 1

3 2

Sample Output 1

2 1 3

Since A=(1,2), the happiness of P is 2, which is the greatest happiness achievable, so the output meets the requirement.

Sample Input 2

3 1

Sample Output 2

1 2 3

Since A=(1,1), the happiness of P is 1, which is the greatest happiness achievable, so the output meets the requirement.

Problem Statement

For an integer sequence X=(X_1,X_2,\dots,X_N) of length N whose elements are all between 1 and N (inclusive), consider the question below, and let f(X) be the answer.

There is an undirected graph G with N vertices (and possibly multi-edges and self-loops). G has N edges, the i-th of which connects Vertex i and Vertex X_i. Find the number of connected components in G.

You are given an integer sequence A=(A_1,A_2,\dots,A_N) of length N, where each A_i is an integer between 1 and N (inclusive) or -1.

Consider an integer sequence X=(X_1,X_2,\dots,X_N) of length N whose elements are all between 1 and N such that A_i \neq -1 \Rightarrow A_i = X_i. Find the sum of f(X) over all such X, modulo 998244353.

Constraints

• 1 \le N \le 2000
• A_i is between 1 and N (inclusive) or -1.
• All values in input are integers.

Sample Input 1

3
-1 1 3

Sample Output 1

5

There are three sequences X satisfying the requirement, as follows.

• X=(1,1,3), for which the answer to the question is 2.
• X=(2,1,3), for which the answer to the question is 2.
• X=(3,1,3), for which the answer to the question is 1.

Thus, the answer is 2+2+1=5.

Sample Input 2

1
1

Sample Output 2

1

Sample Input 3

8
-1 3 -1 -1 8 -1 -1 -1

Sample Output 3

433760

Problem Statement

We have a grid with N \times M squares. You will fill every square with an integer between 1 and 25 (inclusive). Let a_{i,j} be the integer to be written in the square at the i-th row from the top and j-th column from the left.

Find a way to fill the squares to satisfy the condition below. It can be proved that, under the Constraints of this problem, such a way always exists.

• For any integers 1\leq x_1 < x_2\leq N,1\leq y_1 < y_2 \leq M, it must not be the case that a_{x_1,y_1},a_{x_1,y_2},a_{x_2,y_1},a_{x_2,y_2} are all equal.

Constraints

• 2 \leq N , M \leq 500
• All values in input are integers.

Sample Input 1

2 3

Sample Output 1

1 1 1
1 2 3

(x_1,x_2,y_1,y_2) can be one of (1,2,1,2),(1,2,2,3),(1,2,1,3).

For any of them, the numbers written in the squares are not all equal, so this output satisfies the condition.

Problem Statement

Find the number of permutations P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N) that satisfy the following, modulo 998244353, for each K=0,1,2,\dots,N-1.

• There are exactly K integers i such that 1 \le i \le N-1 and |P_i - P_{i+1}|=M.

Constraints

• 2 \le N \le 250000
• 1 \le M \le N-1
• All values in input are integers.

Sample Input 1

3 1

Sample Output 1

0 4 2 

• For K=0, the condition is satisfied by no permutations P.
• For K=1, the condition is satisfied by four permutations P: (1,3,2),(2,1,3),(2,3,1),(3,1,2).
• For K=2, the condition is satisfied by two permutations P: (1,2,3),(3,2,1).

Sample Input 2

4 3

Sample Output 2

12 12 0 0 

Sample Input 3

10 5

Sample Output 3

1263360 1401600 710400 211200 38400 3840 0 0 0 0