Problem Statement

Given are a character S, which is Y or N, and another character T, which is A, B, or C.

If S is Y, print T uppercased.

If S is N, print T as it is.

Constraints

• S is Y or N.
• T is a, b, or c.

Sample Input 1

Y
a

Sample Output 1

A

Since S is Y, we should print T - which is a - uppercased, that is, A.

Sample Input 2

N
b

Sample Output 2

b

Since S is Y, we should print T - which is b - as it is.

Problem Statement

We have a grid with H horizontal rows and W vertical columns of squares, where each square is tidy or untidy.

You will now place a mattress on this grid.

The mattress can be placed on two horizontally or vertically adjacent tidy squares in the grid.

Given are integers H, W, and H strings S_i of length W each. If the j-th character of S_i is ., the square at the i-th row from the top and the j-th column from the left is tidy; if the j-th character of S_i is #, the square at the i-th row from the top and the j-th column from the left is untidy.

Find the number of ways to choose the position for the mattress.

Constraints

• 2 \leq H \leq 100
• 2 \leq W \leq 100
• S_i is a string of length W consisting of . and #.

Sample Input 1

2 3
..#
#..

Sample Output 1

3

We have the following three choices:

• the 1-st and 2-nd squares from the left in the 1-st row from the top;
• the 2-nd and 3-rd squares from the left in the 2-nd row from the top; and
• the 1-st and 2-nd squares from the top in the 2-nd column the left.

Sample Input 2

2 2
.#
#.

Sample Output 2

0

Problem Statement

Given is a number sequence of length N: p_1, ..., p_N.

For each i=1, 2, ..., N, find the minimum non-negative integer that is not equal to any of the numbers p_1, ..., p_i.

Constraints

• 1 \leq N \leq 200,000
• 0 \leq p_i \leq 200,000
• All values in input are integers.

Sample Input 1

4
1 1 0 2

Sample Output 1

0
0
2
3

• The minimum non-negative integer that is not equal to p_1=1 is 0.
• The minimum non-negative integer that is not equal to any of p_1=1, p_2=1 is 0.
• The minimum non-negative integer that is not equal to any of p_1=1, p_2=1, p_3=0 is 2.
• The minimum non-negative integer that is not equal to any of p_1=1, p_2=1, p_3=0, p_4=2 is 3.

Sample Input 2

10
5 4 3 2 1 0 7 7 6 6

Sample Output 2

0
0
0
0
0
6
6
6
8
8

Problem Statement

Given are integers N, A, and B.

We will place a white square whose side is of length N on the coordinate plane so that the vertices are at (0, 0), (N, 0), (0, N), and (N, N).

Then, we will place a blue square whose side is of length A and a red square whose side is of length B so that these squares are inside the white square (including its boundary).

Here, each side of these squares must be parallel to the x- or y-axis.

Additionally, each vertex of red and blue squares must be at an integer point.

Find the number of ways to place red and blue squares so that they do not strictly overlap (they may share boundary with each other), modulo 1,000,000,007.

Solve this problem for T test cases in each input file.

Constraints

• 1 \leq T \leq 10^5
• 1 \leq N \leq 10^9
• 1 \leq A \leq N
• 1 \leq B \leq N
• All values in input are integers.

Sample Input 1

3
3 1 2
4 2 2
331895368 154715807 13941326

Sample Output 1

20
32
409369707

For example, in the first test case, there are 9 ways to place the blue squares and 4 ways to place the red squares, ignoring overlap.

Wherever we place the red square, there are 4 ways to place the blue square so that it strictly overlaps with the red square.

Thus, there are 9 \times 4 - 4 \times 4 = 20 ways to place red and blue squares so that they do not strictly overlap.

Note that the squares may share boundary with each other. For example, when the bottom-left vertices of blue and red squares are (0, 0) and (0, 1), respectively, the squares do not strictly overlap.

Problem Statement

We have a grid with H horizontal rows and W vertical columns of squares, where each square is tidy or untidy.

You will now place lamps on zero or more tidy squares in this grid.

A lamp will lighten the squares in each of the four directions - up, down, left, and right - to the point just before an edge of the grid or an untidy square is reached for the first time (the untidy square will not be lighted). The lamp will also lighten the square on which it is placed.

Given are integers H, W, and H strings S_i of length W each. If the j-th character of S_i is ., the square at the i-th row from the top and the j-th column from the left is tidy; if the j-th character of S_i is #, the square at the i-th row from the top and the j-th column from the left is untidy.

Let K be the number of tidy squares. There are 2^K ways to place the lamps in total. Assume that, for each of these 2^K ways, the number of squares lightened by one or more lamps is computed. Find the sum of those numbers modulo 1,000,000,007.

Constraints

• 1 \leq H \leq 2000
• 1 \leq W \leq 2000
• S_i is a string of length W consisting of . and #.

Sample Input 1

1 5
..#..

Sample Output 1

48

There are 16 ways to place the lamps in total.

• In 9 of the ways (where at least one of the 1-st and 2-nd squares from the left contains a lamp and at least one of the 4-th and 5-th squares from the left contains a lamp), 4 squares will be lighted.
• In 3 of the ways (where at least one of the 1-st and 2-nd squares from the left contains a lamp but none of the 4-th and 5-th squares from the left contains a lamp), 2 squares will be lighted.
• In another 3 of the ways (where none of the 1-st and 2-nd squares from the left contains a lamp but at least one of the 4-th and 5-th squares from the left contains a lamp), 2 squares will be lighted.
• In 1 of the ways (where no square contains a lamp), 0 squares will be lighted.

The sum in question is 4 \times 9 + 2 \times 3 + 2 \times 3 + 0 \times 1 = 48.

Sample Input 2

2 3
..#
#..

Sample Output 2

52

Problem Statement

There are N continuous random variables x_i (1 ≤ i ≤ N), each of which follows the continuous uniform distribution on the interval [L_i, R_i]. (That is, x_i is a random variable that can take any real value between L_i and R_i (inclusive) with equal probability.)

Let E be the expected value of the maximum of these N random variables. Under the constraints in this problem, it can be proved that E \times (N+1)! \times \prod_{i=1}^N (R_i - L_i) is a positive integer. Find this value modulo 1,000,000,007.

Constraints

• 1 ≤ N ≤ 1000
• 0 ≤ L_i < R_i ≤ 10^9
• All values in input are integers.

Sample Input 1

1
1 2

Sample Output 1

3

The expected value of the maximum of these random variables - there is actually just one in this case - is equal to the median of the range of the values the variable can take, that is, E = \frac{3}{2}.

Thus, the correct output is E \times (N+1)! \times (R_1 - L_1) = E \times 2 = 3.

Sample Input 2

2
1 2
1 2

Sample Output 2

10

The expected value in question is E = \frac{5}{3}.

Sample Input 3

2
1 2
2 4

Sample Output 3

36

Sample Input 4

5
40 96
81 92
16 384
32 768
65 536

Sample Output 4

52776507