Problem Statement

Snuke has N integers. Among them, the smallest is A, and the largest is B. We are interested in the sum of those N integers. How many different possible sums there are?

Constraints

• 1 ≤ N,A,B ≤ 10^9
• A and B are integers.

Sample Input 1

4 4 6

Sample Output 1

5

There are five possible sums: 18=4+4+4+6, 19=4+4+5+6, 20=4+5+5+6, 21=4+5+6+6 and 22=4+6+6+6.

Sample Input 2

5 4 3

Sample Output 2

0

Sample Input 3

1 7 10

Sample Output 3

0

Sample Input 4

1 3 3

Sample Output 4

1

Problem Statement

Skenu constructed a building that has N floors. The building has an elevator that stops at every floor.

There are buttons to control the elevator, but Skenu thoughtlessly installed only one button on each floor - up or down. This means that, from each floor, one can only go in one direction. If S_i is U, only "up" button is installed on the i-th floor and one can only go up; if S_i is D, only "down" button is installed on the i-th floor and one can only go down.

The residents have no choice but to go to their destination floors via other floors if necessary. Find the sum of the following numbers over all ordered pairs of two floors (i,j): the minimum number of times one needs to take the elevator to get to the j-th floor from the i-th floor.

Constraints

• 2 ≤ |S| ≤ 10^5
• S_i is either U or D.
• S_1 is U.
• S_{|S|} is D.

Sample Input 1

UUD

Sample Output 1

7

From the 1-st floor, one can get to the 2-nd floor by taking the elevator once.

From the 1-st floor, one can get to the 3-rd floor by taking the elevator once.

From the 2-nd floor, one can get to the 1-st floor by taking the elevator twice.

From the 2-nd floor, one can get to the 3-rd floor by taking the elevator once.

From the 3-rd floor, one can get to the 1-st floor by taking the elevator once.

From the 3-rd floor, one can get to the 2-nd floor by taking the elevator once.

The sum of these numbers of times, 7, should be printed.

Sample Input 2

UUDUUDUD

Sample Output 2

77

Problem Statement

Nuske has a grid with N rows and M columns of squares. The rows are numbered 1 through N from top to bottom, and the columns are numbered 1 through M from left to right. Each square in the grid is painted in either blue or white. If S_{i,j} is 1, the square at the i-th row and j-th column is blue; if S_{i,j} is 0, the square is white. For every pair of two blue square a and b, there is at most one path that starts from a, repeatedly proceeds to an adjacent (side by side) blue square and finally reaches b, without traversing the same square more than once.

Phantom Thnook, Nuske's eternal rival, gives Q queries to Nuske. The i-th query consists of four integers x_{i,1}, y_{i,1}, x_{i,2} and y_{i,2} and asks him the following: when the rectangular region of the grid bounded by (and including) the x_{i,1}-th row, x_{i,2}-th row, y_{i,1}-th column and y_{i,2}-th column is cut out, how many connected components consisting of blue squares there are in the region?

Process all the queries.

Constraints

• 1 ≤ N,M ≤ 2000
• 1 ≤ Q ≤ 200000
• S_{i,j} is either 0 or 1.
• S_{i,j} satisfies the condition explained in the statement.
• 1 ≤ x_{i,1} ≤ x_{i,2} ≤ N(1 ≤ i ≤ Q)
• 1 ≤ y_{i,1} ≤ y_{i,2} ≤ M(1 ≤ i ≤ Q)

Sample Input 1

3 4 4
1101
0110
1101
1 1 3 4
1 1 3 1
2 2 3 4
1 2 2 4

Sample Output 1

3
2
2
2

In the first query, the whole grid is specified. There are three components consisting of blue squares, and thus 3 should be printed.

In the second query, the region within the red frame is specified. There are two components consisting of blue squares, and thus 2 should be printed. Note that squares that belong to the same component in the original grid may belong to different components.

Sample Input 2

5 5 6
11010
01110
10101
11101
01010
1 1 5 5
1 2 4 5
2 3 3 4
3 3 3 3
3 1 3 5
1 1 3 4

Sample Output 2

3
2
1
1
3
2

Problem Statement

Nukes has an integer that can be represented as the bitwise OR of one or more integers between A and B (inclusive). How many possible candidates of the value of Nukes's integer there are?

Constraints

• 1 ≤ A ≤ B < 2^{60}
• A and B are integers.

Sample Input 1

7
9

Sample Output 1

4

In this case, A=7 and B=9. There are four integers that can be represented as the bitwise OR of a non-empty subset of {7, 8, 9}: 7, 8, 9 and 15.

Sample Input 2

65
98

Sample Output 2

63

Sample Input 3

271828182845904523
314159265358979323

Sample Output 3

68833183630578410

Problem Statement

Takahashi is an expert of Clone Jutsu, a secret art that creates copies of his body.

On a number line, there are N copies of Takahashi, numbered 1 through N. The i-th copy is located at position X_i and starts walking with velocity V_i in the positive direction at time 0.

Kenus is a master of Transformation Jutsu, and not only can he change into a person other than himself, but he can also transform another person into someone else.

Kenus can select some of the copies of Takahashi at time 0, and transform them into copies of Aoki, another Ninja. The walking velocity of a copy does not change when it transforms. From then on, whenever a copy of Takahashi and a copy of Aoki are at the same coordinate, that copy of Takahashi transforms into a copy of Aoki.

Among the 2^N ways to transform some copies of Takahashi into copies of Aoki at time 0, in how many ways will all the copies of Takahashi become copies of Aoki after a sufficiently long time? Find the count modulo 10^9+7.

Constraints

• 1 ≤ N ≤ 200000
• 1 ≤ X_i,V_i ≤ 10^9(1 ≤ i ≤ N)
• X_i and V_i are integers.
• All X_i are distinct.
• All V_i are distinct.

Sample Input 1

3
2 5
6 1
3 7

Sample Output 1

6

All copies of Takahashi will turn into copies of Aoki after a sufficiently long time if Kenus transforms one of the following sets of copies of Takahashi into copies of Aoki: (2), (3), (1,2), (1,3), (2,3) and (1,2,3).

Sample Input 2

4
3 7
2 9
8 16
10 8

Sample Output 2

9

Problem Statement

Kenus, the organizer of International Euclidean Olympiad, is seeking a pair of two integers that requires many steps to find its greatest common divisor using the Euclidean algorithm.

You are given Q queries. The i-th query is represented as a pair of two integers X_i and Y_i, and asks you the following: among all pairs of two integers (x,y) such that 1 ≤ x ≤ X_i and 1 ≤ y ≤ Y_i, find the maximum Euclidean step count (defined below), and how many pairs have the maximum step count, modulo 10^9+7.

Process all the queries. Here, the Euclidean step count of a pair of two non-negative integers (a,b) is defined as follows:

• (a,b) and (b,a) have the same Euclidean step count.
• (0,a) has a Euclidean step count of 0.
• If a > 0 and a ≤ b, let p and q be a unique pair of integers such that b=pa+q and 0 ≤ q < a. Then, the Euclidean step count of (a,b) is the Euclidean step count of (q,a) plus 1.

Constraints

• 1 ≤ Q ≤ 3 × 10^5
• 1 ≤ X_i,Y_i ≤ 10^{18}(1 ≤ i ≤ Q)

Sample Input 1

3
4 4
6 10
12 11

Sample Output 1

2 4
4 1
4 7

In the first query, (2,3), (3,2), (3,4) and (4,3) have a Euclidean step count of 2. No pairs have a step count of more than 2.

In the second query, (5,8) has a Euclidean step count of 4.

In the third query, (5,8), (8,5), (7,11), (8,11), (11,7), (11,8), (12,7) have a Euclidean step count of 4.

Sample Input 2

10
1 1
2 2
5 1000000000000000000
7 3
1 334334334334334334
23847657 23458792534
111111111 111111111
7 7
4 19
9 10

Sample Output 2

1 1
1 4
4 600000013
3 1
1 993994017
35 37447
38 2
3 6
3 9
4 2