Problem Statement

How many integer sequences of length N, A=(A_1, \ldots, A_N), satisfy all of the conditions below?

• 1\le A_i \le M (1 \le i \le N)

• \displaystyle\sum _{i=1}^N A_i \leq K

Since the count can get enormous, find it modulo 998244353.

Constraints

• 1 \leq N, M \leq 50
• N \leq K \leq NM
• All values in input are integers.

Sample Input 1

2 3 4

Sample Output 1

6

The following six sequences satisfy the conditions.

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

Sample Input 2

31 41 592

Sample Output 2

798416518

Be sure to print the count modulo 998244353.

Problem Statement

You are given a string S of length N consisting of 0 and 1.
Move the K-th 1-block from the beginning in S to immediately after the (K-1)-th 1-block, and print the resulting string.

It is guaranteed that S contains at least K 1-blocks.

Here is a more precise description.

• Let S_{l\ldots r} denote the substring of S from the l-th character through the r-th character.
• We define a substring S_{l\ldots r} of S to be a 1-block if it satisfies all of the following conditions:
  • S_l = S_{l+1} = \cdots = S_r = 1
  • l = 1 or S_{l-1} = 0
  • r = N or S_{r+1} = 0

• Suppose that all 1-blocks in S are S_{l_1\ldots r_1}, \ldots, S_{l_m\ldots r_m}, where l_1 < l_2 < \cdots < l_m.

  Then, we define the length N string T, obtained by moving the K-th 1-block to immediately after the (K-1)-th 1-block, as follows:

  • T_i = S_i for 1 \leq i \leq r_{K-1}
  • T_i = 1 for r_{K-1} + 1 \leq i \leq r_{K-1} + (r_K - l_K) + 1
  • T_i = 0 for r_{K-1} + (r_K - l_K) + 2 \leq i \leq r_K
  • T_i = S_i for r_K + 1 \leq i \leq N

Constraints

• 1 \leq N \leq 5 \times 10^5
• S is a string of length N consisting of 0 and 1.
• 2 \leq K
• S contains at least K 1-blocks.

Sample Input 1

15 3
010011100011001

Sample Output 1

010011111000001

S has four 1-blocks: from the 2nd to the 2nd character, from the 5th to the 7th character, from the 11th to the 12th character, and from the 15th to the 15th character.

Sample Input 2

10 2
1011111111

Sample Output 2

1111111110

Problem Statement

Takahashi has many balls, on which nothing is written, and one bag. Initially, the bag is empty. Takahashi will do Q operations, each of which is of one of the following three types.

• Type 1: Write an integer X_i on a blank ball and put it in the bag.
• Type 2: For each ball in the bag, replace the integer written on it with that integer plus X_i.
• Type 3: Pick up the ball with the smallest integer in the bag (if there are multiple such balls, pick up one of them). Record the integer written on this ball and throw it away.

For each 1\leq i\leq Q, you are given the type P_i of the i-th operation and the value of X_i if the operation is of Type 1 or 2. Print the integers recorded in the operations of Type 3 in order.

Constraints

• 1 \leq Q \leq 2\times 10^5
• 1 \leq P_i \leq 3
• 1 \leq X_i \leq 10^9
• All values in input are integers.
• There is one or more i such that P_i=3.
• If P_i=3, the bag contains at least one ball just before the i-th operation.

Sample Input 1

5
1 3
1 5
3
2 2
3

Sample Output 1

3
7

Takahashi will do the following operations.

• Write 3 on a ball and put it in the bag.
• Write 5 on a ball and put it in the bag.
• The bag now contains a ball with 3 and another with 5. Pick up the ball with the smaller of them, or 3. Record 3 and throw it away.
• The bag now contains just a ball with 5. Replace this integer with 5+2=7.
• The bag now contains just a ball with 7. Pick up this ball, record 7, and throw it away.

Therefore, we should print 3 and 7, in the order they are recorded.

Sample Input 2

6
1 1000000000
2 1000000000
2 1000000000
2 1000000000
2 1000000000
3

Sample Output 2

5000000000

Note that the outputs may not fit into a 32-bit integer.

Problem Statement

There is a directed graph with N vertices numbered 1 to N and N edges.
The out-degree of every vertex is 1, and the edge from vertex i points to vertex a_i.
Count the number of pairs of vertices (u, v) such that vertex v is reachable from vertex u.

Here, vertex v is reachable from vertex u if there exists a sequence of vertices w_0, w_1, \dots, w_K of length K+1 that satisfies the following conditions. In particular, if u = v, it is always reachable.

• w_0 = u.
• w_K = v.
• For every 0 \leq i \lt K, there is an edge from vertex w_i to vertex w_{i+1}.

Constraints

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

Sample Input 1

4
2 1 1 4

Sample Output 1

8

The vertices reachable from vertex 1 are vertices 1, 2.
The vertices reachable from vertex 2 are vertices 1, 2.
The vertices reachable from vertex 3 are vertices 1, 2, 3.
The vertex reachable from vertex 4 is vertex 4.
Therefore, the number of pairs of vertices (u, v) such that vertex v is reachable from vertex u is 8.
Note that the edge from vertex 4 is a self-loop, that is, it points to vertex 4 itself.

Sample Input 2

5
2 4 3 1 2

Sample Output 2

14

Sample Input 3

10
6 10 4 1 5 9 8 6 5 1

Sample Output 3

41

Problem Statement

A DDoS-type string is a string of length 4 consisting of uppercase and lowercase English letters satisfying both of the following conditions.

• The first, second, and fourth characters are uppercase English letters, and the third character is a lowercase English letter.
• The first and second characters are equal.

For instance, DDoS and AAaA are DDoS-type strings, while neither ddos nor IPoE is.

You are given a string S consisting of uppercase and lowercase English letters and ?. Let q be the number of occurrences of ? in S. There are 52^q strings that can be obtained by independently replacing each ? in S with an uppercase or lowercase English letter. Among these strings, find the number of ones that do not contain a DDoS-type string as a subsequence, modulo 998244353.

Notes

A subsequence of a string is a string obtained by removing zero or more characters from the string and concatenating the remaining characters without changing the order.
For instance, AC is a subsequence of ABC, while RE is not a subsequence of ECR.

Constraints

• S consists of uppercase English letters, lowercase English letters, and ?.
• The length of S is between 4 and 3\times 10^5, inclusive.

Sample Input 1

DD??S

Sample Output 1

676

When at least one of the ?s is replaced with a lowercase English letter, the resulting string will contain a DDoS-type string as a subsequence.

Sample Input 2

????????????????????????????????????????

Sample Output 2

858572093

Find the count modulo 998244353.

Sample Input 3

?D??S

Sample Output 3

136604