Problem Statement

We have an integer sequence A, whose length is N.

Find the number of the non-empty contiguous subsequences of A whose sums are 0. Note that we are counting the ways to take out subsequences. That is, even if the contents of some two subsequences are the same, they are counted individually if they are taken from different positions.

Constraints

• 1 \leq N \leq 2 \times 10^5
• -10^9 \leq A_i \leq 10^9
• All values in input are integers.

Sample Input 1

6
1 3 -4 2 2 -2

Sample Output 1

3

There are three contiguous subsequences whose sums are 0: (1,3,-4), (-4,2,2) and (2,-2).

Sample Input 2

7
1 -1 1 -1 1 -1 1

Sample Output 2

12

In this case, some subsequences that have the same contents but are taken from different positions are counted individually. For example, three occurrences of (1, -1) are counted.

Sample Input 3

5
1 -2 3 -4 5

Sample Output 3

0

There are no contiguous subsequences whose sums are 0.

Problem Statement

Snuke has two boards, each divided into a grid with N rows and N columns. For both of these boards, the square at the i-th row from the top and the j-th column from the left is called Square (i,j).

There is a lowercase English letter written in each square on the first board. The letter written in Square (i,j) is S_{i,j}. On the second board, nothing is written yet.

Snuke will write letters on the second board, as follows:

• First, choose two integers A and B ( 0 \leq A, B < N ).
• Write one letter in each square on the second board. Specifically, write the letter written in Square ( i+A, j+B ) on the first board into Square (i,j) on the second board. Here, the k-th row is also represented as the (N+k)-th row, and the k-th column is also represented as the (N+k)-th column.

After this operation, the second board is called a good board when, for every i and j ( 1 \leq i, j \leq N ), the letter in Square (i,j) and the letter in Square (j,i) are equal.

Find the number of the ways to choose integers A and B ( 0 \leq A, B < N ) such that the second board is a good board.

Constraints

• 1 \leq N \leq 300
• S_{i,j} ( 1 \leq i, j \leq N ) is a lowercase English letter.

Sample Input 1

2
ab
ca

Sample Output 1

2

For each pair of A and B, the second board will look as shown below:

The second board is a good board when (A,B) = (0,1) or (A,B) = (1,0), thus the answer is 2.

Sample Input 2

4
aaaa
aaaa
aaaa
aaaa

Sample Output 2

16

Every possible choice of A and B makes the second board good.

Sample Input 3

5
abcde
fghij
klmno
pqrst
uvwxy

Sample Output 3

0

No possible choice of A and B makes the second board good.

Problem Statement

There are N squares lining up in a row, numbered 1 through N from left to right. Initially, all squares are white. We also have N-1 painting machines, numbered 1 through N-1. When operated, Machine i paints Square i and i+1 black.

Snuke will operate these machines one by one. The order in which he operates them is represented by a permutation of (1, 2, ..., N-1), P, which means that the i-th operated machine is Machine P_i.

Here, the score of a permutation P is defined as the number of machines that are operated before all the squares are painted black for the first time, when the machines are operated in the order specified by P. Snuke has not decided what permutation P to use, but he is interested in the scores of possible permutations. Find the sum of the scores over all possible permutations for him. Since this can be extremely large, compute the sum modulo 10^9+7.

Constraints

• 2 \leq N \leq 10^6

Sample Input 1

4

Sample Output 1

16

There are six possible permutations as P. Among them, P = (1, 3, 2) and P = (3, 1, 2) have a score of 2, and the others have a score of 3. Thus, the answer is 2 \times 2 + 3 \times 4 = 16.

Sample Input 2

2

Sample Output 2

1

There is only one possible permutation: P = (1), which has a score of 1.

Sample Input 3

5

Sample Output 3

84

Sample Input 4

100000

Sample Output 4

341429644

Problem Statement

There are N apartments along a number line, numbered 1 through N. Apartment i is located at coordinate X_i. Also, the office of AtCoder Inc. is located at coordinate S. Every employee of AtCoder lives in one of the N apartments. There are P_i employees who are living in Apartment i.

All employees of AtCoder are now leaving the office all together. Since they are tired from work, they would like to get home by the company's bus. AtCoder owns only one bus, but it can accommodate all the employees. This bus will leave coordinate S with all the employees and move according to the following rule:

• Everyone on the bus casts a vote on which direction the bus should proceed, positive or negative. (The bus is autonomous and has no driver.) Each person has one vote, and abstaining from voting is not allowed. Then, the bus moves a distance of 1 in the direction with the greater number of votes. If a tie occurs, the bus moves in the negative direction. If there is an apartment at the coordinate of the bus after the move, all the employees who live there get off.

• Repeat the operation above as long as there is one or more employees on the bus.

For a specific example, see Sample Input 1.

The bus takes one seconds to travel a distance of 1. The time required to vote and get off the bus is ignorable.

Every employee will vote so that he himself/she herself can get off the bus at the earliest possible time. Strictly speaking, when a vote is taking place, each employee see which direction results in the earlier arrival at his/her apartment, assuming that all the employees follow the same strategy in the future. Based on this information, each employee makes the optimal choice, but if either direction results in the arrival at the same time, he/she casts a vote to the negative direction.

Find the time the bus will take from departure to arrival at the last employees' apartment. It can be proved that, given the positions of the apartments, the numbers of employees living in each apartment and the initial position of the bus, the future movement of the bus is uniquely determined, and the process will end in a finite time.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq S \leq 10^9
• 1 \leq X_1 < X_2 < ... < X_N \leq 10^9
• X_i \neq S ( 1 \leq i \leq N )
• 1 \leq P_i \leq 10^9 ( 1 \leq i \leq N )
• All values in input are integers.

Sample Input 1

3 2
1 3
3 4
4 2

Sample Output 1

4

Assume that the bus moves in the negative direction first. Then, the coordinate of the bus changes from 2 to 1, and the employees living in Apartment 1 get off. The movement of the bus after that is obvious: it just continues moving in the positive direction. Thus, if the bus moves in the negative direction first, the coordinate of the bus changes as 2 → 1 → 2 → 3 → 4 from departure. The time it takes to get home for the employees living in Apartment 1, 2, 3 are 1, 3, 4 seconds, respectively.

Next, assume that the bus moves in the positive direction first. Then, the coordinate of the bus changes from 2 to 3, and the employees living in Apartment 2 get off. Afterwards, the bus starts heading to Apartment 1, because there are more employees living in Apartment 1 than in Apartment 3. Then, after arriving at Apartment 1, the bus heads to Apartment 3. Thus, if the bus moves in the positive direction first, the coordinate of the bus changes as 2 → 3 → 2 → 1 → 2 → 3 → 4 from departure. The time it takes to get home for the employees living in Apartment 1, 2, 3 are 3, 1, 6 seconds, respectively.

Therefore, in the beginning, the employees living in Apartment 1 or 3 will try to move the bus in the negative direction. On the other hand, the employees living in Apartment 2 will try to move the bus in the positive direction in the beginning. There are a total of 3 + 2 = 5 employees living in Apartment 1 and 3 combined, which is more than those living in Apartment 2, which is 4. Thus, the bus will move in the negative direction first, and the coordinate of the bus will change as 2 → 1 → 2 → 3 → 4 from departure.

Sample Input 2

6 4
1 10
2 1000
3 100000
5 1000000
6 10000
7 100

Sample Output 2

21

Since the numbers of employees living in different apartments are literally off by a digit, the bus consistently head to the apartment where the most number of employees on the bus lives.

Sample Input 3

15 409904902
94198000 15017
117995501 7656764
275583856 313263626
284496300 356635175
324233841 607
360631781 148
472103717 5224
497641071 34695
522945827 816241
554305668 32
623788284 22832
667409501 124410641
876731548 12078
904557302 291749534
918215789 5

Sample Output 3

2397671583

Problem Statement

Snuke has an integer sequence A whose length is N. He likes permutations of (1, 2, ..., N), P, that satisfy the following condition:

• P_i \leq A_i for all i ( 1 \leq i \leq N ).

Snuke is interested in the inversion numbers of such permutations. Find the sum of the inversion numbers over all permutations that satisfy the condition. Since this can be extremely large, compute the sum modulo 10^9+7.

Notes

The inversion number of a sequence Z whose length N is the number of pairs of integers i and j ( 1 \leq i < j \leq N ) such that Z_i > Z_j.

Constraints

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

Sample Input 1

3
2 3 3

Sample Output 1

4

There are four permutations that satisfy the condition: (1,2,3), (1,3,2), (2,1,3) and (2,3,1). The inversion numbers of these permutations are 0, 1, 1 and 2, respectively, for a total of 4.

Sample Input 2

6
4 2 5 1 6 3

Sample Output 2

7

Only one permutation (4,2,5,1,6,3) satisfies the condition. The inversion number of this permutation is 7, so the answer is 7.

Sample Input 3

5
4 4 4 4 4

Sample Output 3

0

No permutation satisfies the condition.

Sample Input 4

30
22 30 15 20 10 29 11 29 28 11 26 10 18 28 22 5 29 16 24 24 27 10 21 30 29 19 28 27 18 23

Sample Output 4

848414012

Problem Statement

Snuke has a rooted tree with N vertices, numbered 1 through N. Vertex 1 is the root of the tree, and the parent of Vertex i ( 2\leq i \leq N ) is Vertex P_i ( P_i < i ). There is a number, 0 or 1, written on each vertex. The number written on Vertex i is V_i.

Snuke would like to arrange the vertices of this tree in a horizontal row. Here, for every vertex, there should be no ancestor of that vertex to the right of that vertex.

After arranging the vertices, let X be the sequence obtained by reading the numbers written on the vertices from left to right in the arrangement. Snuke would like to minimize the inversion number of X. Find the minimum possible inversion number of X.

Notes

The inversion number of a sequence Z whose length N is the number of pairs of integers i and j ( 1 \leq i < j \leq N ) such that Z_i > Z_j.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq P_i < i ( 2 \leq i \leq N )
• 0 \leq V_i \leq 1 ( 1 \leq i \leq N )
• All values in input are integers.

Sample Input 1

6
1 1 2 3 3
0 1 1 0 0 0

Sample Output 1

4

When the vertices are arranged in the order 1, 3, 5, 6, 2, 4, X will be (0, 1, 0, 0, 1, 0), whose inversion number is 4. It is impossible to have fewer inversions, so the answer is 4.

Sample Input 2

1

0

Sample Output 2

0

X = (0), whose inversion number is 0.

Sample Input 3

15
1 2 3 2 5 6 2 2 9 10 1 12 13 12
1 1 1 0 1 1 0 0 1 0 0 1 1 0 0

Sample Output 3

31