Problem Statement

You are given a string S of length N consisting of characters A and B.

You can perform the following two types of operations zero or more times in any order:

• Choose a (contiguous) substring ABA in S and replace it with A.
• Choose a (contiguous) substring BAB in S and replace it with B.

Find, modulo 10^9+7, the number of possible strings S after performing the operations.

Constraints

• 1 \leq N \leq 250000
• S is a string of length N consisting of characters A and B.

Sample Input 1

4
ABAB

Sample Output 1

2

The two possible strings S after the operations are as follows:

• ABAB: This string can be obtained by performing zero operations.
• AB: The 1st to 3rd characters of S=ABAB are ABA. Replacing them with A results in S=AB.

Here, the 2nd to 4th characters of S=ABAB are BAB, so you can also replace them with B. Note, however, that the resulting AB does not count multiple times.

Sample Input 2

1
A

Sample Output 2

1

No operations can be performed.

Sample Input 3

17
BBABABAABABAAAABA

Sample Output 3

18

Sample Input 4

100
ABAABAABABBABAABAABAABABBABBABBABBABBABBABBABBABBABBABBABBABBABBABAABABAABABBABBABABBABAABAABAABAABA

Sample Output 4

415919090

Remember to take the result modulo 10^9+7.

Problem Statement

You are given a permutation P=(P_1,P_2,\cdots,P_N) of (1,2,\cdots,N). Additionally, you are given an integer K.

You can perform the following operation zero or more times:

• Choose integers l and r (1 \leq l < r \leq N). Here, the pair (l,r) must satisfy all of the following conditions:
  • K \leq r-l.
  • P_l > P_r at the time of the operation.
  • The pair (l,r) has never been chosen before.
• Then, swap the values of P_l and P_r.

You want to maximize the number of operations. Find one way to achieve this.

Constraints

• 2 \leq N \leq 500
• 1 \leq K \leq N-1
• (P_1,P_2,\cdots,P_N) is a permutation of (1,2,\cdots,N).
• All input values are integers.

Sample Input 1

3 1
3 2 1

Sample Output 1

3
2 3
1 3
1 2

In this example, the maximum number of operations is 3. The operations in the sample output proceed as follows:

• 1st operation: Choose (l,r)=(2,3). We have 1 \leq 3-2 and P_2 > P_3, and (2,3) has not been chosen before, so the conditions are satisfied. Swap P_2 and P_3, resulting in P=(3,1,2).
• 2nd operation: Choose (l,r)=(1,3). We have 1 \leq 3-1 and P_1 > P_3, and (1,3) has not been chosen before, so the conditions are satisfied. Swap P_1 and P_3, resulting in P=(2,1,3).
• 3rd operation: Choose (l,r)=(1,2). We have 1 \leq 2-1 and P_1 > P_2, and (1,2) has not been chosen before, so the conditions are satisfied. Swap P_1 and P_2, resulting in P=(1,2,3).

Sample Input 2

5 4
1 4 3 2 5

Sample Output 2

0

Sample Input 3

4 2
4 1 2 3

Sample Output 3

2
1 4
1 3

Sample Input 4

10 5
8 7 6 10 9 3 1 5 2 4

Sample Output 4

15
3 8
2 8
3 10
3 9
1 8
2 10
2 9
2 7
1 10
5 10
1 9
4 10
4 9
1 7
1 6

Problem Statement

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

You will perform the following operation exactly once:

• Choose a non-empty subsequence of A (not necessarily contiguous) and replace it with its cumulative sums. More precisely, first choose a sequence of indices (i_1,i_2,\cdots,i_k) such that 1 \leq i_1 < i_2 < \cdots < i_k \leq N. The length of the sequence k (1 \leq k \leq N) can be chosen freely. Then, for each j (1 \leq j \leq k), replace the value of A_{i_j} with \sum_{1 \leq x \leq j} A_{i_x}. This replacement is done simultaneously for all chosen indices.

Find, modulo 10^9+7, the number of possible sequences A after the operation.

Constraints

• 1 \leq N \leq 100
• -10 \leq A_i \leq 10
• All input values are integers.

Sample Input 1

3
1 1 2

Sample Output 1

4

The possible sequences A after the operation are as follows:

• A=(1,1,2): This can be achieved with k=1 and (i_1)=(1).
• A=(1,2,2): This can be achieved with k=2 and (i_1,i_2)=(1,2).
• A=(1,1,3): This can be achieved with k=2 and (i_1,i_2)=(1,3).
• A=(1,2,4): This can be achieved with k=3 and (i_1,i_2,i_3)=(1,2,3).

Sample Input 2

4
1 -1 1 -1

Sample Output 2

8

Sample Input 3

5
0 0 0 0 0

Sample Output 3

1

Sample Input 4

40
2 -2 1 3 -3 -1 -2 -3 0 -1 -2 0 -3 0 0 2 0 -1 2 -2 -2 -1 3 -2 -2 -2 2 3 2 -3 0 -2 2 1 3 0 -1 0 -2 -3

Sample Output 4

420429545

Problem Statement

You are given an integer sequence A=(A_1,A_2,\cdots,A_N) of length N. Answer the following Q queries.

• The i-th query: You are given integers L_i and R_i. Solve the following problem for B=(A_{L_i},A_{L_i+1},\cdots,A_{R_i}).
  • Divide B into three non-empty contiguous subsequences. For each contiguous subsequence, let us find the maximum value of its elements. Find the minimum possible sum of these maximum values. Here, the constraints of the problem force the length of B to be at least 3, so there is always at least one way to divide it into three non-empty contiguous subsequences.

Constraints

• 3 \leq N \leq 250000
• 1 \leq Q \leq 250000
• 1 \leq A_i \leq 10^8
• 1 \leq L_i \leq R_i \leq N
• R_i - L_i \geq 2
• All input values are integers.

Sample Input 1

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

Sample Output 1

10
5
6
9
8

Let us explain the first query. We have B=(4,3,1,1,4,5,2). If you divide it into (4,3),(1,1),(4,5,2), the maximum values of the contiguous subsequences are 4,1,5, respectively, and their sum is 10. There is no way to make this sum smaller, so the answer to this query is 10.

Sample Input 2

10 15
8 3 8 10 1 5 3 1 6 4
4 6
2 5
6 9
8 10
2 9
4 10
1 5
1 8
1 3
4 8
1 10
2 10
6 10
2 6
2 6

Sample Output 2

16
14
12
11
17
17
19
14
19
14
17
17
12
16
16

Problem Statement

You are given an integer sequence A=(A_1,A_2,\cdots,A_N) of length N. Here, it is guaranteed that 0 \leq A_i < i for each i.

The score and cost of a permutation P=(P_1,P_2,\cdots,P_N) of (1,2,\cdots,N) are defined as follows:

• The score of P is the length of a longest increasing subsequence of P.
• The cost of P is the number of integers i (1 \leq i \leq N) that satisfy the following condition:
  • There are fewer than A_i integers j such that j < i and P_j > P_i.

For each k=1,2,\cdots,N, solve the following problem:

• Find the minimum cost of a permutation P whose score is at least k.

Constraints

• 1 \leq N \leq 250000
• 0 \leq A_i < i
• All input values are integers.

Sample Input 1

4
0 1 2 1

Sample Output 1

0 0 1 3

For each k, a solution P is as follows:

• k=1: If P=(4,2,1,3), then P has the score of 2 and the cost of 0.
• k=2: If P=(4,3,1,2), then P has the score of 2 and the cost of 0.
• k=3: If P=(4,1,2,3), then P has the score of 3 and the cost of 1.
• k=4: If P=(1,2,3,4), then P has the score of 4 and the cost of 3.

Sample Input 2

3
0 0 0

Sample Output 2

0 0 0

Sample Input 3

5
0 1 2 3 4

Sample Output 3

0 1 2 3 4

Sample Input 4

11
0 0 2 3 4 5 3 7 8 2 10

Sample Output 4

0 0 0 1 2 3 4 5 7 8 9

Problem Statement

You are given integers N and A.

You will perform the following operations:

• Generate N real numbers uniformly at random between 0 and 1, inclusive. All generations are independent, and the random numbers are uniformly distributed.
• Call the generated N real numbers x_1, x_2, \cdots, x_N in ascending order. That is, 0 \leq x_1 \leq x_2 \leq \cdots \leq x_N \leq 1.
• Your score is given by the following formula:

Calculate the expected value, modulo 10^9+7, of the score.

Constraints

• 1 \leq N \leq 10^4
• 1 \leq A \leq 5 \times 10^4
• All input values are integers.

Sample Input 1

2 1

Sample Output 1

666666673

The expected value of the score is 5/3.

Sample Input 2

1 1

Sample Output 2

1

Sample Input 3

2 2

Sample Output 3

500000005

Sample Input 4

3 2

Sample Output 4

142857147

Sample Input 5

5 3

Sample Output 5

758371066

Sample Input 6

10000 12345

Sample Output 6

32201773