Problem Statement

You are given a positive integer N.

For i=1,2,\ldots,N, calculate (-1)^i \times i^3, and find the sum of these N values.

That is, find \displaystyle \sum_{i=1}^N (-1)^i \times i^3.

Constraints

• N is an integer between 1 and 10, inclusive.

Sample Input 1

3

Sample Output 1

-20

• When i=1: (-1)^i\times i^3=-1.
• When i=2: (-1)^i\times i^3=8.
• When i=3: (-1)^i\times i^3=-27.

Therefore, output -1 + 8 - 27 = -20.

Sample Input 2

9

Sample Output 2

-425

Sample Input 3

10

Sample Output 3

575

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N. Here, each element of A is either -1 or an integer between 1 and N, inclusive.

Determine whether there exists an integer sequence P=(P_1,P_2,\ldots,P_N) of length N that satisfies all of the following conditions, and if it exists, find one.

• P is a permutation of (1,2,\ldots,N).
• For i=1,2,\ldots,N, if A_i \neq -1, then P_i=A_i holds.

Constraints

• 1\le N\le 10
• A_i=-1 or 1\le A_i \le N
• All input values are integers.

Sample Input 1

4
-1 -1 2 -1

Sample Output 1

Yes
3 1 2 4

P=(3,1,2,4) satisfies all conditions.

Besides this, P=(1,3,2,4) or P=(4,3,2,1) also satisfies all conditions.

Sample Input 2

5
-1 -1 1 -1 1

Sample Output 2

No

There is no P that satisfies all conditions.

Sample Input 3

7
3 -1 4 -1 5 -1 2

Sample Output 3

Yes
3 7 4 1 5 6 2

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N.

Process Q queries in order. There are two types of queries, given in the following formats:

• 1 c: Perform the operation of moving the first element of A to the end c times.
• 2 l r: Output the value of \displaystyle \sum_{i=l}^r A_i.

Constraints

• 1\le N\le 2\times 10^5
• 1\le Q\le 2\times 10^5
• 1\le A_i \le 10^9
• 1\le c\le N
• 1\le l\le r \le N
• At least one query of the second type exists.
• All input values are integers.

Sample Input 1

4 3
3 1 4 5
2 1 3
1 1
2 2 3

Sample Output 1

8
9

Each query is processed as follows:

• First query: A_1+A_2+A_3=3+1+4=8, so output 8.
• Second query: A=(3,1,4,5) changes to A=(1,4,5,3).
• Third query: A_2+A_3=4+5=9, so output 9.

Sample Input 2

5 7
1 2 4 8 16
2 1 5
1 4
1 5
2 1 5
2 2 4
1 1
2 3 3

Sample Output 2

31
31
7
4

Problem Statement

There is a grid with H rows and W columns. We call the cell at the i-th row from the top (1\leq i\leq H) and j-th column from the left (1\leq j\leq W) as cell (i,j).

Initially, cell (i,j) is colored black if S_{i,j} is # and white if it is ..

Perform the following operation 10^{100} times:

• Let T be the set of cells that are colored white and have exactly one adjacent cell colored black. Color each cell in T black. Here, two cells (i_1,j_1) and (i_2,j_2) are adjacent if and only if |i_1-i_2|+|j_1-j_2|=1.

Find the number of cells that are colored black after all operations are completed.

Constraints

• 2\leq H,W
• HW\leq 3\times 10^5
• H and W are integers.
• S_{i,j} is # or ..

Sample Input 1

9 9
.........
.........
.........
.........
....#....
.........
.........
.........
.........

Sample Output 1

57

The grid changes as follows through the operations. (The number above represents the operation count. The first ten operations are displayed.)

Eventually, 57 cells are colored black.

Sample Input 2

2 2
..
..

Sample Output 2

0

Sample Input 3

10 10
..........
....#.....
#.......#.
......#...
.......#..
.....#....
..........
..........
..#...#...
.......#..

Sample Output 3

64

Problem Statement

You are given a positive integer N and a sequence of positive integers C=(C_1,C_2,\ldots,C_N) of length N.

Find, modulo a given positive integer M, the number of sequences of positive integers that satisfy all of the following conditions.

• All elements of the sequence are between 1 and N, inclusive.
• For each i=1,2,\ldots,N, the value i appears exactly C_i times in the sequence.

T test cases are given, so find the answer for each. M is common to all T test cases.

Constraints

• 1\leq T\leq 10^5
• 2\leq M\leq 10^9
• 1\leq N
• 1\leq C_i
• \sum_{i=1}^N C_i\leq 5000
• The sum of N over all test cases is at most 3\times 10^5.
• All input values are integers.

Sample Input 1

3 1000000000
2
2 2
5
1 1 1 1 1
6
1 2 3 4 5 6

Sample Output 1

6
120
230379200

For the first test case, the sequences that satisfy the conditions are (1,1,2,2),(1,2,1,2),(1,2,2,1),(2,1,1,2),(2,1,2,1),(2,2,1,1), which is six sequences.

Sample Input 2

3 998244353
1
1
3
4 2 5
10
500 500 500 500 500 500 500 500 500 500

Sample Output 2

1
6930
261233246

Problem Statement

You are given a string T of length N consisting of lowercase English letters.

Output, modulo 998244353, the number of sequences of strings s=(s_0,s_1,\ldots,s_N) that satisfy all of the following conditions.

• s_0 is an empty string.
• For i=1,2,\ldots,N, the string s_{i} is obtained by inserting one arbitrary character at an arbitrary position (possibly beginning or end) in s_{i-1}.
• s_N=T

Constraints

• 1\leq N\leq 22
• N is an integer.
• T is a string of length N consisting of lowercase English letters.

Sample Input 1

3
aab

Sample Output 1

3

The sequences s that satisfy the conditions are the following three:

• s=(\texttt{""}, \texttt{"a"} ,\texttt{"aa"} ,\texttt{"aab"} )
• s=(\texttt{""}, \texttt{"a"} ,\texttt{"ab"} ,\texttt{"aab"} )
• s=(\texttt{""}, \texttt{"b"} ,\texttt{"ab"} ,\texttt{"aab"} )

Sample Input 2

7
atcoder

Sample Output 2

5040

Sample Input 3

22
atcoderbeginnercontest

Sample Output 3

115732070

Problem Statement

You are given positive integers N,M and a sequence of non-negative integers A=(A_1,A_2,\ldots,A_N) of length N.

Find \displaystyle \sum_{x=0}^{M-1} \min_{1\le i\le N} \left(x\oplus A_i \right).

Here, x\oplus A_i represents the bitwise \mathrm{XOR} of x and A_i.

Constraints

• 1\le N\le 2\times 10^5
• 1\le M\le 10^9
• 0\le A_i \le 10^9
• All input values are integers.

Sample Input 1

2 4
1 2

Sample Output 1

2

• When x=0: x\oplus A_1=1,x\oplus A_2= 2, so \displaystyle \min_{1\le i\le N} \left(x\oplus A_i \right) = 1.
• When x=1: x\oplus A_1=0,x\oplus A_2= 3, so \displaystyle \min_{1\le i\le N} \left(x\oplus A_i \right) = 0.
• When x=2: x\oplus A_1=3,x\oplus A_2= 0, so \displaystyle \min_{1\le i\le N} \left(x\oplus A_i \right) = 0.
• When x=3: x\oplus A_1=2,x\oplus A_2= 1, so \displaystyle \min_{1\le i\le N} \left(x\oplus A_i \right) = 1.

Therefore, output 1+0+0+1=2.

Sample Input 2

6 5
0 1 2 3 4 5

Sample Output 2

0

Sample Input 3

10 8762
347 883 264 816 533 306 190 880 624 279

Sample Output 3

34912221