Problem Statement

There are three cards on the desk, each with a positive integer written on it. The integers on the cards are A, B, and C.

You have chosen two cards and picked them up.

Find the maximum possible sum of the integers written on the picked cards.

Constraints

• 1 \leq A,B,C \leq 100
• All values in input are integers.

Sample Input 1

3 4 5

Sample Output 1

9

If you pick up two cards with 4 and 5, the sum of the integers will be 4+5=9.

There is no way to pick up cards with a greater sum, so we should print 9.

Sample Input 2

6 6 6

Sample Output 2

12

Whichever two cards you choose, the sum of the integers will be 12.

Sample Input 3

99 99 98

Sample Output 3

198

Problem Statement

There is a container with A cyan balls. Takahashi will do the following operation as many times as he likes (possibly zero times):

• add B cyan balls and C red balls into the container.

Takahashi's objective is to reach a situation where the number of cyan balls in the container is at most D times the number of red balls in it.

Determine whether the objective is achievable. If it is achievable, find the minimum number of operations needed to achieve it.

Constraints

• 1 \leq A,B,C,D \leq 10^5
• All values in input are integers.

Sample Input 1

5 2 3 2

Sample Output 1

2

Before the first operation, the container has 5 cyan balls and 0 red balls. Since 5 is greater than 0 multiplied by D=2, Takahashi's objective is not yet achieved.

Just after the first operation, the container has 7 cyan balls and 3 red balls. Since 7 is greater than 3 multiplied by 2, the objective is still not achieved.

Just after the second operation, the container has 9 cyan balls and 6 red balls. Since 9 is not greater than 6 multiplied by 2, the objective is achieved.

Thus, the answer is 2.

Sample Input 2

6 9 2 3

Sample Output 2

-1

No matter how many times Takahashi repeats the operation, his objective will never be achieved.

Problem Statement

You are given N intervals numbered 1 through N, that are as follows:

• if t_i=1, Interval i is [l_i,r_i];
• if t_i=2, Interval i is [l_i,r_i);
• if t_i=3, Interval i is (l_i,r_i];
• if t_i=4, Interval i is (l_i,r_i).

How many pairs of integers (i,j) satisfying 1 \leq i \lt j \leq N are there such that Interval i and Interval j intersect?

Constraints

• 2 \leq N \leq 2000
• 1 \leq t_i \leq 4
• 1 \leq l_i \lt r_i \leq 10^9
• All values in input are integers.

Sample Input 1

3
1 1 2
2 2 3
3 2 4

Sample Output 1

2

As defined in the Problem Statement, Interval 1 is [1,2], Interval 2 is [2,3), and Interval 3 is (2,4].

There are two pairs of integers (i,j) such that Interval i and Interval j intersect: (1,2) and (2,3). For the first pair, the intersection is [2,2], and for the second pair, the intersection is (2,3).

Sample Input 2

19
4 210068409 221208102
4 16698200 910945203
4 76268400 259148323
4 370943597 566244098
1 428897569 509621647
4 250946752 823720939
1 642505376 868415584
2 619091266 868230936
2 306543999 654038915
4 486033777 715789416
1 527225177 583184546
2 885292456 900938599
3 264004185 486613484
2 345310564 818091848
1 152544274 521564293
4 13819154 555218434
3 507364086 545932412
4 797872271 935850549
2 415488246 685203817

Sample Output 2

102

Problem Statement

You are given two sets S=\{(a_1,b_1),(a_2,b_2),\ldots,(a_N,b_N)\} and T=\{(c_1,d_1),(c_2,d_2),\ldots,(c_N,d_N)\} of N points each on a two-dimensional plane.

Determine whether it is possible to do the following operations on S any number of times (possibly zero) in any order so that S matches T.

• Choose a real number p\ (0 \lt p \lt 360) and rotate every point in S p degrees clockwise about the origin.
• Choose real numbers q and r and move every point in S by q in the x-direction and by r in the y-direction. Here, q and r can be any real numbers, be it positive, negative, or zero.

Constraints

• 1 \leq N \leq 100
• -10 \leq a_i,b_i,c_i,d_i \leq 10
• (a_i,b_i) \neq (a_j,b_j) if i \neq j.
• (c_i,d_i) \neq (c_j,d_j) if i \neq j.
• All values in input are integers.

Sample Input 1

3
0 0
0 1
1 0
2 0
3 0
3 1

Sample Output 1

Yes

The figure below shows the given sets of points, where the points in S and T are painted red and green, respectively:

In this case, we can match S with T as follows:

1. Rotate every point in S 270 degrees clockwise about the origin.
2. Move every point in S by 3 in the x-direction and by 0 in the y-direction.

Sample Input 2

3
1 0
1 1
3 0
-1 0
-1 1
-3 0

Sample Output 2

No

The figure below shows the given sets of points:

Although S and T are symmetric about the y-axis, we cannot match S with T by rotations and translations as stated in Problem Statement.

Sample Input 3

4
0 0
2 9
10 -2
-6 -7
0 0
2 9
10 -2
-6 -7

Sample Output 3

Yes

Sample Input 4

6
10 5
-9 3
1 -5
-6 -5
6 9
-9 0
-7 -10
-10 -5
5 4
9 0
0 -10
-10 -2

Sample Output 4

Yes

Problem Statement

Given is a sequence A of N numbers. Find the number of ways to separate A into some number of non-empty contiguous subsequence B_1, B_2, \ldots, B_k so that the following condition is satisfied:

• For every i\ (1 \leq i \leq k), the sum of elements in B_i is divisible by i.

Since the count can be enormous, print it modulo (10^9+7).

Constraints

• 1 \leq N \leq 3000
• 1 \leq A_i \leq 10^{15}
• All values in input are integers.

Sample Input 1

4
1 2 3 4

Sample Output 1

3

We have three ways to separate the sequence, as follows:

• (1),(2),(3),(4)
• (1,2,3),(4)
• (1,2,3,4)

Sample Input 2

5
8 6 3 3 3

Sample Output 2

5

Sample Input 3

10
791754273866483 706434917156797 714489398264550 918142301070506 559125109706263 694445720452148 648739025948445 869006293795825 718343486637033 934236559762733

Sample Output 3

15

The values in input may not fit into a 32-bit integer type.

Problem Statement

You have a tree with N vertices, numbered 1 through N. The i-th edge connects Vertex u_i and Vertex v_i.

You will choose some vertices (possibly none) and place a takahashi in each of them to guard the tree. A takahashi placed at Vertex x will guard x itself and the vertices directly connected to x by an edge.

There are 2^N ways to choose vertices for placing takahashi. In how many of them will there be exactly K vertices guarded by one or more takahashi?

Find this count and print it modulo (10^9+7) for each K=0,1,\ldots,N.

Constraints

• 1 \leq N \leq 2000
• 1 \leq u_i \lt v_i \leq N
• The given graph is a tree.
• All values in input are integers.

Sample Input 1

3
1 3
1 2

Sample Output 1

1
0
2
5

There are eight ways to choose vertices for placing takahashi, as follows:

• Place a takahashi at no vertices, guarding no vertices.
• Place a takahashi at Vertex 1, guarding all vertices.
• Place a takahashi at Vertex 2, guarding Vertices 1 and 2.
• Place a takahashi at Vertex 3, guarding Vertices 1 and 3.
• Place a takahashi at Vertices 1 and 2, guarding all vertices.
• Place a takahashi at Vertices 1 and 3, guarding all vertices.
• Place a takahashi at Vertices 2 and 3, guarding all vertices.
• Place a takahashi at all vertices, guarding all vertices.

Sample Input 2

5
1 3
4 5
1 5
2 3

Sample Output 2

1
0
2
5
7
17

Sample Input 3

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

Sample Output 3

1
0
3
8
15
32
68
110
196
266
325