Problem Statement

Takahashi has A untasty cookies containing antidotes, B tasty cookies containing antidotes and C tasty cookies containing poison.

Eating a cookie containing poison results in a stomachache, and eating a cookie containing poison while having a stomachache results in a death. As he wants to live, he cannot eat one in such a situation. Eating a cookie containing antidotes while having a stomachache cures it, and there is no other way to cure stomachaches.

Find the maximum number of tasty cookies that Takahashi can eat.

Constraints

• 0 \leq A,B,C \leq 10^9
• A,B and C are integers.

Sample Input 1

3 1 4

Sample Output 1

5

We can eat all tasty cookies, in the following order:

• A tasty cookie containing poison
• An untasty cookie containing antidotes
• A tasty cookie containing poison
• A tasty cookie containing antidotes
• A tasty cookie containing poison
• An untasty cookie containing antidotes
• A tasty cookie containing poison

Sample Input 2

5 2 9

Sample Output 2

10

Sample Input 3

8 8 1

Sample Output 3

9

Problem Statement

Takahashi Lake has a perimeter of L. On the circumference of the lake, there is a residence of the lake's owner, Takahashi. Each point on the circumference of the lake has a coordinate between 0 and L (including 0 but not L), which is the distance from the Takahashi's residence, measured counter-clockwise.

There are N trees around the lake; the coordinate of the i-th tree is X_i. There is no tree at coordinate 0, the location of Takahashi's residence.

Starting at his residence, Takahashi will repeat the following action:

• If all trees are burnt, terminate the process.
• Specify a direction: clockwise or counter-clockwise.
• Walk around the lake in the specified direction, until the coordinate of a tree that is not yet burnt is reached for the first time.
• When the coordinate with the tree is reached, burn that tree, stay at the position and go back to the first step.

Find the longest possible total distance Takahashi walks during the process.

Partial Score

A partial score can be obtained in this problem:

• 300 points will be awarded for passing the input satisfying N \leq 2000.

Constraints

• 2 \leq L \leq 10^9
• 1 \leq N \leq 2\times 10^5
• 1 \leq X_1 < ... < X_N \leq L-1
• All values in input are integers.

Sample Input 1

10 3
2
7
9

Sample Output 1

15

Takahashi walks the distance of 15 if the process goes as follows:

• Walk a distance of 2 counter-clockwise, burn the tree at the coordinate 2 and stay there.
• Walk a distance of 5 counter-clockwise, burn the tree at the coordinate 7 and stay there.
• Walk a distance of 8 clockwise, burn the tree at the coordinate 9 and stay there.

Sample Input 2

10 6
1
2
3
6
7
9

Sample Output 2

27

Sample Input 3

314159265 7
21662711
77271666
89022761
156626166
160332356
166902656
298992265

Sample Output 3

1204124749

Problem Statement

For an n \times n grid, let (r, c) denote the square at the (r+1)-th row from the top and the (c+1)-th column from the left. A good coloring of this grid using K colors is a coloring that satisfies the following:

• Each square is painted in one of the K colors.
• Each of the K colors is used for some squares.
• Let us number the K colors 1, 2, ..., K. For any colors i and j (1 \leq i \leq K, 1 \leq j \leq K), every square in Color i has the same number of adjacent squares in Color j. Here, the squares adjacent to square (r, c) are ((r-1)\; mod\; n, c), ((r+1)\; mod\; n, c), (r, (c-1)\; mod\; n) and (r, (c+1)\; mod\; n) (if the same square appears multiple times among these four, the square is counted that number of times).

Given K, choose n between 1 and 500 (inclusive) freely and construct a good coloring of an n \times n grid using K colors. It can be proved that this is always possible under the constraints of this problem,

Constraints

• 1 \leq K \leq 1000

Sample Input 1

2

Sample Output 1

3
1 1 1
1 1 1
2 2 2

• Every square in Color 1 has three adjacent squares in Color 1 and one adjacent square in Color 2.
• Every square in Color 2 has two adjacent squares in Color 1 and two adjacent squares in Color 2.

Output such as the following will be judged incorrect:

2
1 2
2 2

3
1 1 1
1 1 1
1 1 1

Sample Input 2

9

Sample Output 2

3
1 2 3
4 5 6
7 8 9

Problem Statement

You are given an integer sequence of length N: A_1,A_2,...,A_N. Let us perform Q operations in order. The i-th operation is described by two integers X_i and Y_i. In this operation, we will choose one of the following two actions and perform it:

• Swap the values of A_{X_i} and A_{Y_i}
• Do nothing

There are 2^Q ways to perform these operations. Find the sum of the inversion numbers of the final sequences for all of these ways to perform operations, modulo 10^9+7.

Here, the inversion number of a sequence P_1,P_2,...,P_M is the number of pairs of integers (i,j) such that 1\leq i < j\leq M and P_i > P_j.

Constraints

• 1 \leq N \leq 3000
• 0 \leq Q \leq 3000
• 0 \leq A_i \leq 10^9(1\leq i\leq N)
• 1 \leq X_i,Y_i \leq N(1\leq i\leq Q)
• X_i\neq Y_i(1\leq i\leq Q)
• All values in input are integers.

Sample Input 1

3 2
1
2
3
1 2
1 3

Sample Output 1

6

There are four ways to perform operations, as follows:

• Do nothing, both in the first and second operations. The final sequence would be 1,2,3, with the inversion number of 0.
• Do nothing in the first operation, then perform the swap in the second. The final sequence would be 3,2,1, with the inversion number of 3.
• Perform the swap in the first operation, then do nothing in the second. The final sequence would be 2,1,3, with the inversion number of 1.
• Perform the swap, both in the first and second operations. The final sequence would be 3,1,2, with the inversion number of 2.

The sum of these inversion numbers, 0+3+1+2=6, should be printed.

Sample Input 2

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

Sample Output 2

36

Sample Input 3

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

Sample Output 3

425

Problem Statement

You are given strings s and t, both of length N. s and t consist of 0 and 1. Additionally, in these strings, the same character never occurs three or more times in a row.

You can modify s by repeatedly performing the following operation:

• Choose an index i (1 \leq i \leq N) freely and invert the i-th character in s (that is, replace 0 with 1, and 1 with 0), under the condition that the same character would not occur three or more times in a row in s after the operation.

Your objective is to make s equal to t. Find the minimum number of operations required.

Constraints

• 1 \leq N \leq 5000
• The lengths of s and t are both N.
• s and t consists of 0 and 1.
• In s and t, the same character never occurs three or more times in a row.

Sample Input 1

4
0011
0101

Sample Output 1

4

One possible solution is 0011 → 1011 → 1001 → 1101 → 0101.

Sample Input 2

1
0
0

Sample Output 2

0

Sample Input 3

8
00110011
10101010

Sample Output 3

10

Problem Statement

There is a sequence of length 2N: A_1, A_2, ..., A_{2N}. Each A_i is either -1 or an integer between 1 and 2N (inclusive). Any integer other than -1 appears at most once in {A_i}.

For each i such that A_i = -1, Snuke replaces A_i with an integer between 1 and 2N (inclusive), so that {A_i} will be a permutation of 1, 2, ..., 2N. Then, he finds a sequence of length N, B_1, B_2, ..., B_N, as B_i = min(A_{2i-1}, A_{2i}).

Find the number of different sequences that B_1, B_2, ..., B_N can be, modulo 10^9 + 7.

Constraints

• 1 \leq N \leq 300
• A_i = -1 or 1 \leq A_i \leq 2N.
• If A_i \neq -1, A_j \neq -1, then A_i \neq A_j. (i \neq j)

Sample Input 1

3
1 -1 -1 3 6 -1

Sample Output 1

5

There are six ways to make {A_i} a permutation of 1, 2, ..., 2N; for each of them, {B_i} would be as follows:

• (A_1, A_2, A_3, A_4, A_5, A_6) = (1, 2, 4, 3, 6, 5): (B_1, B_2, B_3) = (1, 3, 5)
• (A_1, A_2, A_3, A_4, A_5, A_6) = (1, 2, 5, 3, 6, 4): (B_1, B_2, B_3) = (1, 3, 4)
• (A_1, A_2, A_3, A_4, A_5, A_6) = (1, 4, 2, 3, 6, 5): (B_1, B_2, B_3) = (1, 2, 5)
• (A_1, A_2, A_3, A_4, A_5, A_6) = (1, 4, 5, 3, 6, 2): (B_1, B_2, B_3) = (1, 3, 2)
• (A_1, A_2, A_3, A_4, A_5, A_6) = (1, 5, 2, 3, 6, 4): (B_1, B_2, B_3) = (1, 2, 4)
• (A_1, A_2, A_3, A_4, A_5, A_6) = (1, 5, 4, 3, 6, 2): (B_1, B_2, B_3) = (1, 3, 2)

Thus, there are five different sequences that B_1, B_2, B_3 can be.

Sample Input 2

4
7 1 8 3 5 2 6 4

Sample Output 2

1

Sample Input 3

10
7 -1 -1 -1 -1 -1 -1 6 14 12 13 -1 15 -1 -1 -1 -1 20 -1 -1

Sample Output 3

9540576

Sample Input 4

20
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 6 -1 -1 -1 -1 -1 7 -1 -1 -1 -1 -1 -1 -1 -1 -1 34 -1 -1 -1 -1 31 -1 -1 -1 -1 -1 -1 -1 -1

Sample Output 4

374984201