Problem Statement

We have an integer N.

Print an integer x between N and 10^{13} (inclusive) such that, for every integer y between 2 and N (inclusive), the remainder when x is divided by y is 1.

Under the constraints of this problem, there is always at least one such integer x.

Constraints

• All values in input are integers.
• 2 \leq N \leq 30

Sample Input 1

3

Sample Output 1

7

The remainder when 7 is divided by 2 is 1, and the remainder when 7 is divided by 3 is 1, too.

7 is an integer between 3 and 10^{13}, so this is a desirable output.

Sample Input 2

10

Sample Output 2

39916801

Problem Statement

Let S be the concatenation of 10^{10} copies of the string 110. (For reference, the concatenation of 3 copies of 110 is 110110110.)

We have a string T of length N.

Find the number of times T occurs in S as a contiguous substring.

Constraints

• 1 \leq N \leq 2 \times 10^5
• T is a string of length N consisting of 0 and 1.

Sample Input 1

4
1011

Sample Output 1

9999999999

S is so long, so let us instead count the number of times 1011 occurs in the concatenation of 3 copies of 110, that is, 110110110. We can see it occurs twice:

• 1 1011 0110

• 1101 1011 0

Sample Input 2

22
1011011011011011011011

Sample Output 2

9999999993

Problem Statement

We have a permutation P = P_1, P_2, \ldots, P_N of 1, 2, \ldots, N.

You have to do the following N - 1 operations on P, each exactly once, in some order:

• Swap P_1 and P_2.

• Swap P_2 and P_3.

  \vdots

• Swap P_{N-1} and P_N.

Your task is to sort P in ascending order by configuring the order of operations. If it is impossible, print -1 instead.

Constraints

• All values in input are integers.
• 2 \leq N \leq 2 \times 10^5
• P is a permutation of 1, 2, \ldots, N.

Sample Input 1

5
2 4 1 5 3

Sample Output 1

4
2
3
1

The following sequence of operations sort P in ascending order:

• First, swap P_4 and P_5, turning P into 2, 4, 1, 3, 5.
• Then, swap P_2 and P_3, turning P into 2, 1, 4, 3, 5.
• Then, swap P_3 and P_4, turning P into 2, 1, 3, 4, 5.
• Finally, swap P_1 and P_2, turning P into 1, 2, 3, 4, 5.

Sample Input 2

5
5 4 3 2 1

Sample Output 2

-1

Problem Statement

We have a sequence A of N non-negative integers.

Compute the sum of \prod _{i = 1} ^N \dbinom{B_i}{A_i} over all sequences B of N non-negative integers whose sum is at most M, and print it modulo (10^9 + 7).

Here, \dbinom{B_i}{A_i}, the binomial coefficient, denotes the number of ways to choose A_i objects from B_i objects, and is 0 when B_i < A_i.

Constraints

• All values in input are integers.
• 1 \leq N \leq 2000
• 1 \leq M \leq 10^9
• 0 \leq A_i \leq 2000

Sample Input 1

3 5
1 2 1

Sample Output 1

8

There are four sequences B such that \prod _{i = 1} ^N \dbinom{B_i}{A_i} is at least 1:

• B = \{1, 2, 1\}, where \prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{1}{1} \times \dbinom{2}{2} \times \dbinom{1}{1} = 1;

• B = \{2, 2, 1\}, where \prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{2}{1} \times \dbinom{2}{2} \times \dbinom{1}{1} = 2;

• B = \{1, 3, 1\}, where \prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{1}{1} \times \dbinom{3}{2} \times \dbinom{1}{1} = 3;

• B = \{1, 2, 2\}, where \prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{1}{1} \times \dbinom{2}{2} \times \dbinom{2}{1} = 2.

The sum of these is 1 + 2 + 3 + 2 = 8.

Sample Input 2

10 998244353
31 41 59 26 53 58 97 93 23 84

Sample Output 2

642612171

Problem Statement

We have a string S of length N consisting of A, B, and C.

You can do the following operation on S zero or more times:

• Choose i (1 \leq i \leq |S| - 1) such that S_i \neq S_{i + 1}. Replace S_i with the character (among A, B, and C) that is different from both S_i and S_{i + 1}, and remove S_{i + 1} from S.

Find the number of distinct strings that S can be after zero or more operations, and print the count modulo (10^9+7).

Constraints

• 1 \leq N \leq 10^6
• S is a string of length N consisting of A, B, and C.

Sample Input 1

5
ABAAC

Sample Output 1

11

For example, the following sequence of operations turns S into ACB:

• First, choose i=2. We replace S_2 with C and remove S_3, turning S into ACAC.
• Then, choose i=3. We replace S_3 with B and remove S_4, turning S into ACB.

Sample Input 2

50
AACCCCBBBACCCCABABCCCCABACCACACACCACABABBBABABACCB

Sample Output 2

256972022

Problem Statement

We have a permutation P = P_0, P_1, \ldots, P_{N - 1} of 0, 1, \ldots, N - 1.

You can do the following operation on P at most 2 \times 10^5 times:

• Announce an integer i ~ (0 \leq i \leq N - 1). Swap P_i and P_{(i + P_i) \textrm{ mod } N}.

Your task is to sort P in ascending order with this operation. If it is impossible, print -1 instead.

Constraints

• All values in input are integers.
• 2 \leq N \leq 100
• P is a permutation of 0, 1, \ldots, N - 1.

Sample Input 1

8
7 1 2 6 4 0 5 3

Sample Output 1

4
6
0
3
0

This sequence of operations sorts P in ascending order, as follows:

• First, announce i = 6. We swap P_6 (= 5) and P_{(6 + 5) \textrm{ mod } 8} = P_3 (= 6), turning P into 7, 1, 2, 5, 4, 0, 6, 3.

• Then, announce i = 0. We swap P_0 (= 7) and P_{(0 + 7) \textrm{ mod } 8} = P_7 (= 3), turning P into 3, 1, 2, 5, 4, 0, 6, 7.

• Then, announce i = 3. We swap P_3 (= 5) and P_{(3 + 5) \textrm{ mod } 8} = P_0 (= 3), turning P into 5, 1, 2, 3, 4, 0, 6, 7.

• Finally, announce i = 0. We swap P_0 (= 5) and P_{(0 + 5) \textrm{ mod } 8} = P_5 (= 0), turning P into 0, 1, 2, 3, 4, 5, 6, 7.