Problem Statement

There are three airports A, B and C, and flights between each pair of airports in both directions.

A one-way flight between airports A and B takes P hours, a one-way flight between airports B and C takes Q hours, and a one-way flight between airports C and A takes R hours.

Consider a route where we start at one of the airports, fly to another airport and then fly to the other airport.

What is the minimum possible sum of the flight times?

Constraints

• 1 \leq P,Q,R \leq 100
• All values in input are integers.

Sample Input 1

1 3 4

Sample Output 1

4

• The sum of the flight times in the route A \rightarrow B \rightarrow C: 1 + 3 = 4 hours
• The sum of the flight times in the route A \rightarrow C \rightarrow C: 4 + 3 = 7 hours
• The sum of the flight times in the route B \rightarrow A \rightarrow C: 1 + 4 = 5 hours
• The sum of the flight times in the route B \rightarrow C \rightarrow A: 3 + 4 = 7 hours
• The sum of the flight times in the route C \rightarrow A \rightarrow B: 4 + 1 = 5 hours
• The sum of the flight times in the route C \rightarrow B \rightarrow A: 3 + 1 = 4 hours

The minimum of these is 4 hours.

Sample Input 2

3 2 3

Sample Output 2

5

Problem Statement

We have N weights indexed 1 to N. The mass of the weight indexed i is W_i.

We will divide these weights into two groups: the weights with indices not greater than T, and those with indices greater than T, for some integer 1 \leq T < N. Let S_1 be the sum of the masses of the weights in the former group, and S_2 be the sum of the masses of the weights in the latter group.

Consider all possible such divisions and find the minimum possible absolute difference of S_1 and S_2.

Constraints

• 2 \leq N \leq 100
• 1 \leq W_i \leq 100
• All values in input are integers.

Sample Input 1

3
1 2 3

Sample Output 1

0

If T = 2, S_1 = 1 + 2 = 3 and S_2 = 3, with the absolute difference of 0.

Sample Input 2

4
1 3 1 1

Sample Output 2

2

If T = 2, S_1 = 1 + 3 = 4 and S_2 = 1 + 1 = 2, with the absolute difference of 2. We cannot have a smaller absolute difference.

Sample Input 3

8
27 23 76 2 3 5 62 52

Sample Output 3

2

Problem Statement

There is a staircase with N steps. Takahashi is now standing at the foot of the stairs, that is, on the 0-th step. He can climb up one or two steps at a time.

However, the treads of the a_1-th, a_2-th, a_3-th, \ldots, a_M-th steps are broken, so it is dangerous to set foot on those steps.

How many are there to climb up to the top step, that is, the N-th step, without setting foot on the broken steps? Find the count modulo 1\ 000\ 000\ 007.

Constraints

• 1 \leq N \leq 10^5
• 0 \leq M \leq N-1
• 1 \leq a_1 < a_2 < ... < a_M \leq N-1

Sample Input 1

6 1
3

Sample Output 1

4

There are four ways to climb up the stairs, as follows:

• 0 \to 1 \to 2 \to 4 \to 5 \to 6
• 0 \to 1 \to 2 \to 4 \to 6
• 0 \to 2 \to 4 \to 5 \to 6
• 0 \to 2 \to 4 \to 6

Sample Input 2

10 2
4
5

Sample Output 2

0

There may be no way to climb up the stairs without setting foot on the broken steps.

Sample Input 3

100 5
1
23
45
67
89

Sample Output 3

608200469

Be sure to print the count modulo 1\ 000\ 000\ 007.

Problem Statement

There is a grid with H horizontal rows and W vertical columns, and there are obstacles on some of the squares.

Snuke is going to choose one of the squares not occupied by an obstacle and place a lamp on it. The lamp placed on the square will emit straight beams of light in four cardinal directions: up, down, left, and right. In each direction, the beam will continue traveling until it hits a square occupied by an obstacle or it hits the border of the grid. It will light all the squares on the way, including the square on which the lamp is placed, but not the square occupied by an obstacle.

Snuke wants to maximize the number of squares lighted by the lamp.

You are given H strings S_i (1 \leq i \leq H), each of length W. If the j-th character (1 \leq j \leq W) of S_i is #, there is an obstacle on the square at the i-th row from the top and the j-th column from the left; if that character is ., there is no obstacle on that square.

Find the maximum possible number of squares lighted by the lamp.

Constraints

• 1 \leq H \leq 2,000
• 1 \leq W \leq 2,000
• S_i is a string of length W consisting of # and ..
• . occurs at least once in one of the strings S_i (1 \leq i \leq H).

Sample Input 1

4 6
#..#..
.....#
....#.
#.#...

Sample Output 1

8

If Snuke places the lamp on the square at the second row from the top and the second column from the left, it will light the following squares: the first through fifth squares from the left in the second row, and the first through fourth squares from the top in the second column, for a total of eight squares.

Sample Input 2

8 8
..#...#.
....#...
##......
..###..#
...#..#.
##....#.
#...#...
###.#..#

Sample Output 2

13

Problem Statement

You are given a positive integer L in base two. How many pairs of non-negative integers (a, b) satisfy the following conditions?

• a + b \leq L
• a + b = a \text{ XOR } b

Since there can be extremely many such pairs, print the count modulo 10^9 + 7.

Constraints

• L is given in base two, without leading zeros.
• 1 \leq L < 2^{100\ 001}

Sample Input 1

10

Sample Output 1

5

Five pairs (a, b) satisfy the conditions: (0, 0), (0, 1), (1, 0), (0, 2) and (2, 0).

Sample Input 2

1111111111111111111

Sample Output 2

162261460

Problem Statement

There is an arithmetic progression with L terms: s_0, s_1, s_2, ... , s_{L-1}.

The initial term is A, and the common difference is B. That is, s_i = A + B \times i holds.

Consider the integer obtained by concatenating the terms written in base ten without leading zeros. For example, the sequence 3, 7, 11, 15, 19 would be concatenated into 37111519. What is the remainder when that integer is divided by M?

Constraints

• All values in input are integers.
• 1 \leq L, A, B < 10^{18}
• 2 \leq M \leq 10^9
• All terms in the arithmetic progression are less than 10^{18}.

Sample Input 1

5 3 4 10007

Sample Output 1

5563

Our arithmetic progression is 3, 7, 11, 15, 19, so the answer is 37111519 mod 10007, that is, 5563.

Sample Input 2

4 8 1 1000000

Sample Output 2

891011

Sample Input 3

107 10000000000007 1000000000000007 998244353

Sample Output 3

39122908