Problem Statement

In this problem, a date is written as Y-M-D. For example, 2019-11-30 means November 30, 2019.

Integers M_1, D_1, M_2, and D_2 will be given as input.
It is known that the date 2019-M_2-D_2 follows 2019-M_1-D_1.
Determine whether the date 2019-M_1-D_1 is the last day of a month.

Constraints

• Both 2019-M_1-D_1 and 2019-M_2-D_2 are valid dates in the Gregorian calendar.
• The date 2019-M_2-D_2 follows 2019-M_1-D_1.

Sample Input 1

11 16
11 17

Sample Output 1

0

November 16 is not the last day of a month.

Sample Input 2

11 30
12 1

Sample Output 2

1

November 30 is the last day of November.

Problem Statement

Takahashi bought a piece of apple pie at ABC Confiserie. According to his memory, he paid N yen (the currency of Japan) for it.

The consumption tax rate for foods in this shop is 8 percent. That is, to buy an apple pie priced at X yen before tax, you have to pay X \times 1.08 yen (rounded down to the nearest integer).

Takahashi forgot the price of his apple pie before tax, X, and wants to know it again. Write a program that takes N as input and finds X. We assume X is an integer.

If there are multiple possible values for X, find any one of them. Also, Takahashi's memory of N, the amount he paid, may be incorrect. If no value could be X, report that fact.

Constraints

• 1 \leq N \leq 50000
• N is an integer.

Sample Input 1

432

Sample Output 1

400

If the apple pie is priced at 400 yen before tax, you have to pay 400 \times 1.08 = 432 yen to buy one.
Otherwise, the amount you have to pay will not be 432 yen.

Sample Input 2

1079

Sample Output 2

:(

There is no possible price before tax for which you have to pay 1079 yen with tax.

Sample Input 3

1001

Sample Output 3

927

If the apple pie is priced 927 yen before tax, by rounding down 927 \times 1.08 = 1001.16, you have to pay 1001 yen.

Problem Statement

AtCoder Mart sells 1000000 of each of the six items below:

• Riceballs, priced at 100 yen (the currency of Japan) each
• Sandwiches, priced at 101 yen each
• Cookies, priced at 102 yen each
• Cakes, priced at 103 yen each
• Candies, priced at 104 yen each
• Computers, priced at 105 yen each

Takahashi wants to buy some of them that cost exactly X yen in total. Determine whether this is possible.
(Ignore consumption tax.)

Constraints

• 1 \leq X \leq 100000
• X is an integer.

Sample Input 1

615

Sample Output 1

1

For example, we can buy one of each kind of item, which will cost 100+101+102+103+104+105=615 yen in total.

Sample Input 2

217

Sample Output 2

0

No set of items costs 217 yen in total.

Problem Statement

AtCoder Inc. has decided to lock the door of its office with a 3-digit PIN code.

The company has an N-digit lucky number, S. Takahashi, the president, will erase N-3 digits from S and concatenate the remaining 3 digits without changing the order to set the PIN code.

How many different PIN codes can he set this way?

Both the lucky number and the PIN code may begin with a 0.

Constraints

• 4 \leq N \leq 30000
• S is a string of length N consisting of digits.

Sample Input 1

4
0224

Sample Output 1

3

Takahashi has the following options:

• Erase the first digit of S and set 224.
• Erase the second digit of S and set 024.
• Erase the third digit of S and set 024.
• Erase the fourth digit of S and set 022.

Thus, he can set three different PIN codes: 022, 024, and 224.

Sample Input 2

6
123123

Sample Output 2

17

Sample Input 3

19
3141592653589793238

Sample Output 3

329

Problem Statement

N people are standing in a queue, numbered 1, 2, 3, ..., N from front to back. Each person wears a hat, which is red, blue, or green.

The person numbered i says:

• "In front of me, exactly A_i people are wearing hats with the same color as mine."

Assuming that all these statements are correct, find the number of possible combinations of colors of the N people's hats.

Since the count can be enormous, compute it modulo 1000000007.

Constraints

• 1 \leq N \leq 100000
• 0 \leq A_i \leq N-1
• All values in input are integers.

Sample Input 1

6
0 1 2 3 4 5

Sample Output 1

3

We have three possible combinations, as follows:

• Red, Red, Red, Red, Red, Red
• Blue, Blue, Blue, Blue, Blue, Blue
• Green, Green, Green, Green, Green, Green

Sample Input 2

3
0 0 0

Sample Output 2

6

Sample Input 3

54
0 0 1 0 1 2 1 2 3 2 3 3 4 4 5 4 6 5 7 8 5 6 6 7 7 8 8 9 9 10 10 11 9 12 10 13 14 11 11 12 12 13 13 14 14 15 15 15 16 16 16 17 17 17

Sample Output 3

115295190

Problem Statement

Takahashi and Aoki are training for long-distance races in an infinitely long straight course running from west to east.

They start simultaneously at the same point and moves as follows towards the east:

• Takahashi runs A_1 meters per minute for the first T_1 minutes, then runs at A_2 meters per minute for the subsequent T_2 minutes, and alternates between these two modes forever.
• Aoki runs B_1 meters per minute for the first T_1 minutes, then runs at B_2 meters per minute for the subsequent T_2 minutes, and alternates between these two modes forever.

How many times will Takahashi and Aoki meet each other, that is, come to the same point? We do not count the start of the run. If they meet infinitely many times, report that fact.

Constraints

• 1 \leq T_i \leq 100000
• 1 \leq A_i \leq 10^{10}
• 1 \leq B_i \leq 10^{10}
• A_1 \neq B_1
• A_2 \neq B_2
• All values in input are integers.

Sample Input 1

1 2
10 10
12 4

Sample Output 1

1

They will meet just once, \frac{4}{3} minutes after they start, at \frac{40}{3} meters from where they start.

Sample Input 2

100 1
101 101
102 1

Sample Output 2

infinity

They will meet 101, 202, 303, 404, 505, 606, ... minutes after they start, that is, they will meet infinitely many times.

Sample Input 3

12000 15700
3390000000 3810000000
5550000000 2130000000

Sample Output 3

113

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