Problem Statement

Snuke participated in a magic show.

A magician prepared N identical-looking boxes. He put a treasure in one of the boxes, closed the boxes, shuffled them, and numbered them 1 through N.

Since the boxes are shuffled, now Snuke has no idea which box contains the treasure. Snuke wins the game if he opens a box containing the treasure. You may think that if Snuke opens all boxes at once, he can always win the game. However, there are some tricks:

• Snuke must open the boxes one by one. After he opens a box and checks the content of the box, he must close the box before opening the next box.
• He is only allowed to open Box i at most a_i times.
• The magician may secretly move the treasure from a closed box to another closed box, using some magic trick. For simplicity, assume that the magician never moves the treasure while Snuke is opening some box. However, he can move it at any other time (before Snuke opens the first box, or between he closes some box and opens the next box).
• The magician can perform the magic trick at most K times.

Can Snuke always win the game, regardless of the initial position of the treasure and the movements of the magician?

Constraints

• 2 \leq N \leq 50
• 1 \leq K \leq 50
• 1 \leq a_i \leq 100

Sample Input 1

2 1
5 5

Sample Output 1

7
1 1 2 1 2 2 1

If Snuke opens the boxes 7 times in the order 1 \rightarrow 1 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 2 \rightarrow 1, he can always find the treasure regardless of its initial position and the movements of the magician.

Sample Input 2

3 50
5 10 15

Sample Output 2

-1

Problem Statement

Count the number of strings S that satisfy the following constraints, modulo 10^9 + 7.

• The length of S is exactly N.
• S consists of digits (0...9).
• You are given Q intervals. For each i (1 \leq i \leq Q), the integer represented by S[l_i \ldots r_i] (the substring of S between the l_i-th (1-based) character and the r_i-th character, inclusive) must be a multiple of 9.

Here, the string S and its substrings may have leading zeroes. For example, 002019 represents the integer 2019.

Constraints

• 1 \leq N \leq 10^9
• 1 \leq Q \leq 15
• 1 \leq l_i \leq r_i \leq N

Sample Input 1

4
2
1 2
2 4

Sample Output 1

136

For example, S = 9072 satisfies the conditions because both S[1 \ldots 2] = 90 and S[2 \ldots 4] = 072 represent multiples of 9.

Sample Input 2

6
3
2 5
3 5
1 3

Sample Output 2

2720

Sample Input 3

20
10
2 15
5 6
1 12
7 9
2 17
5 15
2 4
16 17
2 12
8 17

Sample Output 3

862268030

Problem Statement

There is an infinitely large triangular grid, as shown below. Each point with integer coordinates contains a lamp.

Initially, only the lamp at (X, 0) was on, and all other lamps were off. Then, Snuke performed the following operation zero or more times:

• Choose two integers x and y. Toggle (on to off, off to on) the following three lamps: (x, y), (x, y+1), (x+1, y).

After the operations, N lamps (x_1, y_1), \cdots, (x_N, y_N) are on, and all other lamps are off. Find X.

Constraints

• 1 \leq N \leq 10^5
• -10^{17} \leq x_i, y_i \leq 10^{17}
• (x_i, y_i) are pairwise distinct.
• The input is consistent with the statement, and you can uniquely determine X.

Sample Input 1

4
-2 1
-2 2
0 1
1 0

Sample Output 1

-1

The following picture shows one possible sequence of operations:

Problem Statement

Red bold fonts show the difference from C1.

There is an infinitely large triangular grid, as shown below. Each point with integer coordinates contains a lamp.

Initially, only the lamp at (X, Y) was on, and all other lamps were off. Then, Snuke performed the following operation zero or more times:

• Choose two integers x and y. Toggle (on to off, off to on) the following three lamps: (x, y), (x, y+1), (x+1, y).

After the operations, N lamps (x_1, y_1), \cdots, (x_N, y_N) are on, and all other lamps are off. Find X and Y.

Constraints

• 1 \leq N \leq 10^4
• -10^{17} \leq x_i, y_i \leq 10^{17}
• (x_i, y_i) are pairwise distinct.
• The input is consistent with the statement, and you can uniquely determine X and Y.

Sample Input 1

4
-2 1
-2 2
0 1
1 0

Sample Output 1

-1 0

The following picture shows one possible sequence of operations:

Problem Statement

Snuke has R red balls and B blue balls. He distributes them into K boxes, so that no box is empty and no two boxes are identical. Compute the maximum possible value of K.

Formally speaking, let's number the boxes 1 through K. If Box i contains r_i red balls and b_i blue balls, the following conditions must be satisfied:

• For each i (1 \leq i \leq K), r_i > 0 or b_i > 0.
• For each i, j (1 \leq i < j \leq K), r_i \neq r_j or b_i \neq b_j.
• \sum r_i = R and \sum b_i = B (no balls can be left outside the boxes).

Constraints

• 1 \leq R, B \leq 10^{9}

Sample Input 1

8 3

Sample Output 1

5

The following picture shows one possible way to achieve K = 5:

Problem Statement

There is a very long bench. The bench is divided into M sections, where M is a very large integer.

Initially, the bench is vacant. Then, M people come to the bench one by one, and perform the following action:

• We call a section comfortable if the section is currently unoccupied and is not adjacent to any occupied sections. If there is no comfortable section, the person leaves the bench. Otherwise, the person chooses one of comfortable sections uniformly at random, and sits there. (The choices are independent from each other).

After all M people perform actions, Snuke chooses an interval of N consecutive sections uniformly at random (from M-N+1 possible intervals), and takes a photo. His photo can be described by a string of length N consisting of X and -: the i-th character of the string is X if the i-th section from the left in the interval is occupied, and - otherwise. Note that the photo is directed. For example, -X--X and X--X- are different photos.

What is the probability that the photo matches a given string s? This probability depends on M. You need to compute the limit of this probability when M goes infinity.

Here, we can prove that the limit can be uniquely written in the following format using three rational numbers p, q, r and e = 2.718 \ldots (the base of natural logarithm):

p + \frac{q}{e} + \frac{r}{e^2}

Your task is to compute these three rational numbers, and print them modulo 10^9 + 7, as described in Notes section.

Notes

When you print a rational number, first write it as a fraction \frac{y}{x}, where x, y are integers and x is not divisible by 10^9 + 7 (under the constraints of the problem, such representation is always possible). Then, you need to print the only integer z between 0 and 10^9 + 6, inclusive, that satisfies xz \equiv y \pmod{10^9 + 7}.

Constraints

• 1 \leq N \leq 1000
• |s| = N
• s consists of X and -.

Sample Input 1

1
X

Sample Output 1

500000004 0 500000003

The probability that a randomly chosen section is occupied converge to \frac{1}{2} - \frac{1}{2e^2}.

Sample Input 2

3
---

Sample Output 2

0 0 0

After the actions, no three consecutive unoccupied sections can be left.

Sample Input 3

5
X--X-

Sample Output 3

0 0 1

The limit is \frac{1}{e^2}.

Sample Input 4

5
X-X-X

Sample Output 4

500000004 0 833333337

The limit is \frac{1}{2} - \frac{13}{6e^2}.

Sample Input 5

20
-X--X--X-X--X--X-X-X

Sample Output 5

0 0 183703705

The limit is \frac{7}{675e^2}.

Sample Input 6

100
X-X-X-X-X-X-X-X-X-X--X-X-X-X-X-X-X-X-X-X-X-X-X-X-X--X--X-X-X-X--X--X-X-X--X-X-X--X-X--X--X-X--X-X-X-

Sample Output 6

0 0 435664291