Problem Statement

A sequence of length A + B, E = (E_1, E_2, \dots, E_{A+B}), that satisfies all of the conditions below is said to be a god sequence.

• E_1 + E_2 + \cdots + E_{A+B} = 0 holds.
• There are exactly A positive integers among E_1, E_2, \dots, E_{A+B}.
• There are exactly B negative integers among E_1, E_2, \dots, E_{A+B}.
• E_1, E_2, \dots, E_{A+B} are all distinct.
• -10^{9} \leq E_i \leq 10^9, E_i \neq 0 holds for every i (1 \leq i \leq A+B).

Construct one god sequence.

We can prove that at least one god sequence exists under Constraints of this problem.

Constraints

• 1 \leq A \leq 1000
• 1 \leq B \leq 1000
• All values in input are integers.

Sample Input 1

1 1

Sample Output 1

1001 -1001

A sequence (1001, -1001) contains A=1 positive integer and B=1 negative integer totaling 1001+(-1001)=0.

It also satisfies the other conditions and thus is a god sequence.

Sample Input 2

1 4

Sample Output 2

-8 -6 -9 120 -97

A sequence (-8, -6, -9, 120, -97) contains A=1 positive integer and B=4 negative integers totaling (-8)+(-6)+(-9)+120+(-97)=0.

It also satisfies the other conditions and thus is a god sequence.

Sample Input 3

7 5

Sample Output 3

323 -320 411 206 -259 298 -177 -564 167 392 -628 151

Problem Statement

There are N buildings along AtCoder road. Initially, the i-th building from the left has A_i stories.

Takahashi, the president of ARC Wrecker, Inc., can do the following operation any number of times, possibly zero:

• Choose a positive integer X that he likes and shoot a cannonball at that height, which decreases by 1 the number of stories in each building with X or more stories.

Find the number of possible final sceneries of buildings, modulo (10^{9} + 7).

We consider two sceneries A and B different when the following holds:

• let P_i be the number of stories of the i-th building from the left in scenery A;
• let Q_i be the number of stories of the i-th building from the left in scenery B;
• we consider sceneries A and B different when P_i \neq Q_i for one or more indices i.

Constraints

• 1 \leq N \leq 100000
• 1 \leq A_i \leq 10^{9}
• All values in input are integers.

Sample Input 1

2
1 2

Sample Output 1

4

There are four possible combinations of heights of the buildings, as follows:

• (Building 1, Building 2) = (0, 0)
• (Building 1, Building 2) = (0, 1)
• (Building 1, Building 2) = (1, 1)
• (Building 1, Building 2) = (1, 2)

Sample Input 2

6
5 3 4 1 5 2

Sample Output 2

32

Sample Input 3

7
314 159 265 358 979 323 846

Sample Output 3

492018656

There are 20192492160000 possible final sceneries. The correct output is that number modulo 10^{9} + 7, which is 492018656.

Problem Statement

We have N blocks arranged in a row, where each block is painted blue, white, or red. The color of the i-th block from the left (1 \leq i \leq N) is represented by a character c_i; B, W, and R stand for blue, white, and red, respectively.

From this situation, we will pile up blue, white, and red blocks to make a pyramid with N steps. The following figure shows an example of this:

Here, we place blocks one by one from bottom to top as follows:

• if the two blocks immediately below a position have the same color, we will place there a block of the same color;
• if the two blocks immediately below a position have different colors, we will place there a block of the color different from those two colors.

What will be the color of the block at the top?

Constraints

• N is an integer satisfying 2 \leq N \leq 400000.
• Each of c_1, c_2, \dots, c_N is B, W, or R.

Sample Input 1

3
BWR

Sample Output 1

W

In this case, we will pile up blocks as follows:

• the 1-st and 2-nd blocks from the left in the bottom row are respectively blue and white, so we place a red block on top of it;
• the 2-nd and 3-rd blocks from the left in the bottom row are respectively white and red, so we place a blue block on top of it;
• the blocks in the 2-nd row from the bottom are respectively red and blue, so we place a white block on top of it.

Thus, the block at the top will be white; we should print W.

Sample Input 2

4
RRBB

Sample Output 2

W

In this case, we will pile up blocks as follows:

• the 1-st and 2-nd blocks from the left in the bottom row are both red, so we place a red block on top of it;
• the 2-nd and 3-rd blocks from the left in the bottom row are respectively red and blue, so we place a white block on top of it;
• the 3-rd and 4-th blocks from the left in the bottom row are both blue, so we place a blue block on top of it;
• the 1-st and 2-nd blocks from the left in the 2-nd row from the bottom are respectively red and white, so we place a blue block on top of it;
• the 2-nd and 3-rd blocks from the left in the 2-nd row from the bottom are respectively white and blue, so we place a red block on top of it;
• the blocks in the 3-rd row from the bottom are respectively blue and red, so we place a white block on top of it.

Thus, the block at the top will be white; we should print W.

Sample Input 3

6
BWWRBW

Sample Output 3

B

The figure below shows the final arrangement of blocks. The block at the top will be blue; we should print B.

Note that this is the case shown as an example in Problem Statement.

Sample Input 4

8
WWBRBBWB

Sample Output 4

R

The figure below shows the final arrangement of blocks. The block at the top will be red; we should print R.

Sample Input 5

21
BWBRRBBRWBRBBBRRBWWWR

Sample Output 5

B

Problem Statement

We have a tree with N vertices, numbered 1, 2, \dots, N. The i-th edge (1 \leq i \leq N-1) connects Vertex A_i and Vertex B_i.

A boy E869120 found this tree and wants to write an integer in each vertex to surprise another boy square1001. For that, the following conditions need to be satisfied, where E_i is the integer written on Vertex i.

Condition 1: E_i \geq 1 (1 \leq i \leq N) holds.
Condition 2: |E_i - E_j| \geq dist(i, j) holds for every pair (i, j) (1 \leq i < j \leq N).
Condition 3: the value \max(E_1, E_2, \dots, E_N) should be minimized while satisfying Conditions 1 and 2.

Here, dist(i, j) is:

• the length of the simple path (the path without repetition of the same vertex) from Vertex i to j.
• In other words, it is the value L where the simple path is q_0 \to q_1 \to q_2 \to \cdots \to q_L (q_0 = i, q_L = j).

Construct one way to write integers that surprises square1001.

Constraints

• 2 \leq N \leq 200000
• 1 \leq A_i < B_i \leq N
• The given graph is a tree.
• All values in input are integers.

Sample Input 1

2
1 2

Sample Output 1

2 1

If we write an integer 2 on Vertex 1 and an integer 1 on Vertex 2, we have dist(1, 2) = 1 and |E_1 - E_2| = 1, satisfying Condition 2.

The other conditions are also satisfied, so we can surprise square1001 this way.

(E_1, E_2) = (1, 2) will also be accepted.

Sample Input 2

4
1 2
1 4
2 3

Sample Output 2

3 2 1 4

(E_1, E_2, E_3, E_4) = (2, 3, 4, 1) will also be accepted.

Problem Statement

How many different sequences of length 2N, A = (A_1, A_2, \dots, A_{2N}), satisfy both of the following conditions?

• The sequence A contains N occurrences of +1 and N occurrences of -1.
• There are exactly K pairs of l and r (1 \leq l \leq r \leq 2N) such that A_l + A_{l+1} + \cdots + A_r = 0.

Constraints

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

Sample Input 1

1 1

Sample Output 1

2

For N = 1, K = 1, two sequences below satisfy the conditions:

• A = (+1, -1)
• A = (-1, +1)

Sample Input 2

2 3

Sample Output 2

2

For N = 2, K = 3, two sequences below satisfy the conditions:

• A = (+1, -1, -1, +1)
• A = (-1, +1, +1, -1)

Sample Input 3

3 7

Sample Output 3

6

For N = 3, K = 7, six sequences below satisfy the conditions:

• A = (+1, -1, +1, -1, -1, +1)
• A = (+1, -1, -1, +1, +1, -1)
• A = (+1, -1, -1, +1, -1, +1)
• A = (-1, +1, +1, -1, +1, -1)
• A = (-1, +1, +1, -1, -1, +1)
• A = (-1, +1, -1, +1, +1, -1)

Sample Input 4

8 24

Sample Output 4

568

Sample Input 5

30 230

Sample Output 5

761128315856702

Sample Input 6

25 455

Sample Output 6

0

For N = 25, K = 455, no sequences satisfy the conditions.

Problem Statement

Mr. AtCoder made a round chocolate cake for his 2N friends. It is radially cut from the center into 2N equal pieces, numbered 0 through 2N-1 in clockwise order.

To give the final touches, he is going to put strawberries on each piece. He has heard what his friends want about it. The friends are numbered 0 through 2N-1, and Friend i (0 \leq i \leq 2N-1) wants the following:

• Piece i, i+1, \dots, i+N-1 have a total of at least A_i strawberries on them (for x \geq 2N, consider Piece x as Piece x-2N).

To fulfill the requests of all his friends, at least how many strawberries should be put on the whole cake?

Constraints

• 1 \leq N \leq 150000
• 0 \leq A_i \leq 5 \times 10^8 \ (0 \leq i \leq 2N-1)
• All values in input are integers.

Sample Input 1

3
2 5 7 4 2 1

Sample Output 1

8

Consider the case we put 1, 0, 1, 4, 2, 0 strawberries on Pieces 0, 1, 2, 3, 4, 5, respectively.

In this case, all requests of the friends are fulfilled, as follows:

• Friend 0: Pieces 0, 1, 2 have a total of 2 strawberries on them, which is not less than A_0 = 2.
• Friend 1: Pieces 1, 2, 3 have a total of 5 strawberries on them, which is not less than A_1 = 5.
• Friend 2: Pieces 2, 3, 4 have a total of 7 strawberries on them, which is not less than A_2 = 7.
• Friend 3: Pieces 3, 4, 5 have a total of 6 strawberries on them, which is not less than A_3 = 4.
• Friend 4: Pieces 4, 5, 0 have a total of 3 strawberries on them, which is not less than A_4 = 2.
• Friend 5: Pieces 5, 0, 1 have a total of 1 strawberry on them, which is not less than A_5 = 1.

Thus, we can fulfill all requests of the friends by putting a total of 8 strawberries on the cake. This is the minimum number of strawberries needed.

Sample Input 2

3
8 0 6 0 9 0

Sample Output 2

12

Consider the case we put 6, 0, 2, 1, 3, 0 strawberries on Pieces 0, 1, 2, 3, 4, 5, respectively.

In this case, all requests of the friends are fulfilled, as follows:

• Friend 0: Pieces 0, 1, 2 have a total of 8 strawberries on them, which is not less than A_0 = 8.
• Friend 1: Pieces 1, 2, 3 have a total of 3 strawberries on them, which is not less than A_1 = 0.
• Friend 2: Pieces 2, 3, 4 have a total of 6 strawberries on them, which is not less than A_2 = 6.
• Friend 3: Pieces 3, 4, 5 have a total of 4 strawberries on them, which is not less than A_3 = 0.
• Friend 4: Pieces 4, 5, 0 have a total of 9 strawberries on them, which is not less than A_4 = 9.
• Friend 5: Pieces 5, 0, 1 have a total of 6 strawberries on them, which is not less than A_5 = 0.

Thus, we can fulfill all requests of the friends by putting a total of 12 strawberries on the cake. This is the minimum number of strawberries needed.

Sample Input 3

5
3 1 5 7 0 8 4 6 4 9

Sample Output 3

12

We can put 0, 0, 0, 4, 0, 1, 1, 1, 0, 5 strawberries on Pieces 0, 1, \dots, 9, respectively, to fulfill all requests of the friends.

In this case, there is a total of 12 strawberries on the cake, which is the minimum number of strawberries needed.

Sample Input 4

1
267503 601617

Sample Output 4

869120

We can put 267503 strawberries on Piece 0 and 601617 strawberries on Piece 1 to fulfill all requests of the friends.

Sample Input 5

8
418940906 38034755 396064111 43044067 356084286 61548818 15301658 35906016 20933120 211233791 30314875 25149642 42550552 104690843 81256233 63578117

Sample Output 5

513119404