Problem Statement

Niwango created a playlist of N songs. The title and the duration of the i-th song are s_i and t_i seconds, respectively. It is guaranteed that s_1,\ldots,s_N are all distinct.

Niwango was doing some work while playing this playlist. (That is, all the songs were played once, in the order they appear in the playlist, without any pause in between.) However, he fell asleep during his work, and he woke up after all the songs were played. According to his record, it turned out that he fell asleep at the very end of the song titled X.

Find the duration of time when some song was played while Niwango was asleep.

Constraints

• 1 \leq N \leq 50
• s_i and X are strings of length between 1 and 100 (inclusive) consisting of lowercase English letters.
• s_1,\ldots,s_N are distinct.
• There exists an integer i such that s_i = X.
• 1 \leq t_i \leq 1000
• t_i is an integer.

Sample Input 1

3
dwango 2
sixth 5
prelims 25
dwango

Sample Output 1

30

• While Niwango was asleep, two songs were played: sixth and prelims.
• The answer is the total duration of these songs, 30.

Sample Input 2

1
abcde 1000
abcde

Sample Output 2

0

• No songs were played while Niwango was asleep.
• In such a case, the total duration of songs is 0.

Sample Input 3

15
ypnxn 279
kgjgwx 464
qquhuwq 327
rxing 549
pmuduhznoaqu 832
dagktgdarveusju 595
wunfagppcoi 200
dhavrncwfw 720
jpcmigg 658
wrczqxycivdqn 639
mcmkkbnjfeod 992
htqvkgkbhtytsz 130
twflegsjz 467
dswxxrxuzzfhkp 989
szfwtzfpnscgue 958
pmuduhznoaqu

Sample Output 3

6348

Problem Statement

There are N slimes standing on a number line. The i-th slime from the left is at position x_i.

It is guaruanteed that 1 \leq x_1 < x_2 < \ldots < x_N \leq 10^{9}.

Niwango will perform N-1 operations. The i-th operation consists of the following procedures:

• Choose an integer k between 1 and N-i (inclusive) with equal probability.
• Move the k-th slime from the left, to the position of the neighboring slime to the right.
• Fuse the two slimes at the same position into one slime.

Find the total distance traveled by the slimes multiplied by (N-1)! (we can show that this value is an integer), modulo (10^{9}+7). If a slime is born by a fuse and that slime moves, we count it as just one slime.

Constraints

• 2 \leq N \leq 10^{5}
• 1 \leq x_1 < x_2 < \ldots < x_N \leq 10^{9}
• x_i is an integer.

Subtasks

• 400 points will be awarded for passing the test cases satisfying N \leq 2000.

Sample Input 1

3
1 2 3

Sample Output 1

5

• With probability \frac{1}{2}, the leftmost slime is chosen in the first operation, in which case the total distance traveled is 2.
• With probability \frac{1}{2}, the middle slime is chosen in the first operation, in which case the total distance traveled is 3.
• The answer is the expected total distance traveled, 2.5, multiplied by 2!, which is 5.

Sample Input 2

12
161735902 211047202 430302156 450968417 628894325 707723857 731963982 822804784 880895728 923078537 971407775 982631932

Sample Output 2

750927044

• Find the expected value multiplied by (N-1)!, modulo (10^9+7).

Problem Statement

There are N children, numbered 1,2,\ldots,N. In the next K days, we will give them some cookies. In the i-th day, we will choose a_i children among the N with equal probability, and give one cookie to each child chosen. (We make these K choices independently.)

Let us define the happiness of the children as c_1 \times c_2 \times \ldots \times c_N, where c_i is the number of cookies received by Child i in the K days. Find the expected happiness multiplied by \binom{N}{a_1} \times \binom{N}{a_2} \times \ldots \times \binom{N}{a_K} (we can show that this value is an integer), modulo (10^{9}+7).

Notes

\binom{n}{k} denotes the number of possible choices of k objects out of given distinct n objects, disregarding order.

Constraints

• 1 \leq N \leq 1000
• 1 \leq K \leq 20
• 1 \leq a_i \leq N

Sample Input 1

3 2
3 2

Sample Output 1

12

• On the first day, all the children 1, 2, and 3 receive one cookie.
• On the second day, two out of the three children 1, 2, and 3 receive one cookie.
• Their happiness is 4 in any case, so the expected happiness is 4. Print this value multiplied by \binom{3}{3} \times \binom{3}{2}, which is 12.

Sample Input 2

856 16
399 263 665 432 206 61 784 548 422 313 848 478 827 26 398 63

Sample Output 2

337587117

• Find the expected value multiplied by \binom{N}{a_1} \times \binom{N}{a_2} \times \ldots \times \binom{N}{a_K}, modulo (10^9+7).

Problem Statement

Niwango has N cards, numbered 1,2,\ldots,N. He will now arrange these cards in a row.

Niwango wants to know if there is a way to arrange the cards while satisfying all the N conditions below. To help him, determine whether such a way exists. If the answer is yes, also find the lexicographically smallest such arrangement.

• To the immediate right of Card 1 (if any) is NOT Card a_1.
• To the immediate right of Card 2 (if any) is NOT Card a_2.
• \vdots
• To the immediate right of Card N (if any) is NOT Card a_N.

Constraints

• 2 \leq N \leq 10^{5}
• 1 \leq a_i \leq N
• a_i \neq i

Sample Input 1

4
2 3 4 1

Sample Output 1

1 3 2 4

• The arrangement (1,2,3,4) is lexicographically smaller than (1,3,2,4), but is invalid, since it violates the condition "to the immediate right of Card 1 is not Card 2."

Sample Input 2

2
2 1

Sample Output 2

-1

• If no arrangements satisfy the conditions, print -1.

Sample Input 3

13
2 3 4 5 6 7 8 9 10 11 12 13 12

Sample Output 3

1 3 2 4 6 5 7 9 8 10 12 11 13

Problem Statement

Niwango bought a piece of land that can be represented as a half-open interval [0, X).

Niwango will lay out N vinyl sheets on this land. The sheets are numbered 1,2, \ldots, N, and they are distinguishable. For Sheet i, he can choose an integer j such that 0 \leq j \leq X - L_i and cover [j, j + L_i) with this sheet.

Find the number of ways to cover the land with the sheets such that no point in [0, X) remains uncovered, modulo (10^9+7). We consider two ways to cover the land different if and only if there is an integer i (1 \leq i \leq N) such that the region covered by Sheet i is different.

Constraints

• 1 \leq N \leq 100
• 1 \leq L_i \leq X \leq 500
• All values in input are integers.

Sample Input 1

3 3
1 1 2

Sample Output 1

10

• If we ignore whether the whole interval is covered, there are 18 ways to lay out the sheets.
• Among them, there are 4 ways that leave [0, 1) uncovered, and 4 ways that leave [2, 3) uncovered.
• Each of the other ways covers the whole interval [0,3), so the answer is 10.

Sample Input 2

18 477
324 31 27 227 9 21 41 29 50 34 2 362 92 11 13 17 183 119

Sample Output 2

134796357

• Find the number of ways modulo (10^9+7).