Problem Statement

Is it possible to get a sum of B when throwing a die with six faces 1,2,\ldots,6 A times?

Constraints

• 1 \leq A \leq 100
• 1 \leq B \leq 1000
• A and B are integers.

Sample Input 1

2 11

Sample Output 1

Yes

There are two ways to get a sum of 11 when throwing a 6-faced die twice:

• getting 6 in the first throw and 5 in the second throw;
• getting 5 in the first throw and 6 in the second throw.

Sample Input 2

2 13

Sample Output 2

No

There is no way to get a sum of 13 when throwing a 6-faced die twice.

Sample Input 3

100 600

Sample Output 3

Yes

Problem Statement

The coins used in the Kingdom of Takahashi are 1!-yen coins, 2!-yen coins, \dots, and 10!-yen coins. Here, N! = 1 \times 2 \times \dots \times N.

Takahashi has 100 of every kind of coin, and he is going to buy a product worth P yen by giving the exact amount without receiving change.

We can prove that there is always such a way to make payment.

At least how many coins does he need to use in his payment?

Constraints

• 1 \leq P \leq 10^7
• P is an integer.

Sample Input 1

9

Sample Output 1

3

By giving one (1! =) 1-yen coin, one (2! =) 2-yen coin, and one (3! =) 6-yen coin, we can make the exact payment for the product worth 9 yen. There is no way to pay this amount using fewer coins.

Sample Input 2

119

Sample Output 2

10

We should use one 1!-yen coin, two 2!-yen coins, three 3!-yen coins, and four 4!-yen coins.

Sample Input 3

10000000

Sample Output 3

24

Problem Statement

There are N citizens in the Kingdom of Takahashi. Each citizen has a national ID number; the ID of the i-th citizen is a_i. Here, all a_i are pairwise different.

Takahashi has K pieces of sweets. He has decided to hand out these pieces to the citizens in the following way until he has no more pieces.

• When he has N or more pieces, hand out one piece to every citizen.
• Otherwise, let K' be the number of pieces he has at the moment, and hand out one piece to each of the citizens with the K' smallest IDs.

When all pieces are handed out, how many pieces will the i-th citizen have?

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq 10^{18}
• 1 \leq a_i \leq 10^9
• All a_i are pairwise different.
• All values in input are integers.

Sample Input 1

2 7
1 8

Sample Output 1

4
3

Takahashi will hand out the pieces as follows.

• Hand out one piece to everyone, leaving Takhashi with 5 pieces.
• Hand out one piece to everyone, leaving Takhashi with 3 pieces.
• Hand out one piece to everyone, leaving Takhashi with 1 piece.
• Hand out one piece to the 1-st citizen, leaving Takhashi with no pieces.

In the end, the 1-st citizen will receive 4 pieces, and the 2-nd citizen will receive 3 pieces.

Sample Input 2

1 3
33

Sample Output 2

3

Since there is just one citizen, Takahashi will hand out all pieces to that 1-st citizen.

Sample Input 3

7 1000000000000
99 8 2 4 43 5 3

Sample Output 3

142857142857
142857142857
142857142858
142857142857
142857142857
142857142857
142857142857

Problem Statement

There are N cities and M roads in the Kingdom of Takahashi.

The cities are numbered 1 through N, and the roads are numbered 1 through M. Road i is a one-way road that leads from City A_i to City B_i, and it takes C_i minutes to go through it.

Let us define f(s, t, k) as the answer to the following query.

• Compute the minimum time needed to get from City s to City t. Here, other than the Cities s and t, it is only allowed to pass through Cities 1 through k. If City t is unreachable or s = t, the answer should be 0.

Compute f(s,t,k) for all triples s,t,k and print the sum of them. More formally, print \displaystyle \sum_{s = 1}^N \sum_{t = 1}^N \sum_{k = 1}^N f(s, t, k).

Constraints

• 1 \leq N \leq 400
• 0 \leq M \leq N(N-1)
• 1 \leq A_i \leq N (1 \leq i \leq M)
• 1 \leq B_i \leq N (1 \leq i \leq M)
• A_i \neq B_i (1 \leq i \leq M)
• 1 \leq C_i \leq 10^6 (1 \leq i \leq M)
• A_i \neq A_j or B_i \neq B_j, if i \neq j.
• All values in input are integers.

Sample Input 1

3 2
1 2 3
2 3 2

Sample Output 1

25

The triples s,t,k such that f(s,t,k) \neq 0 are as follows.

• For k = 1: f(1,2,1) = 3, f(2,3,1) = 2.
• For k = 2: f(1,2,2) = 3, f(2,3,2) = 2, f(1,3,2) = 5.
• For k = 3: f(1,2,3) = 3, f(2,3,3) = 2, f(1,3,3) = 5.

Sample Input 2

3 0

Sample Output 2

0

We have f(s,t,k) = 0 for all s,t,k.

Sample Input 3

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

Sample Output 3

517

Problem Statement

For how many positive integers at most N is the product of the digits at most K?

Constraints

• 1 \leq N \leq 10^{18}
• 1 \leq K \leq 10^9
• All values in input are integers.

Sample Input 1

13 2

Sample Output 1

5

Out of the positive integers at most 13, there are five such that the product of the digits is at most 2: 1, 2, 10, 11, and 12.

Sample Input 2

100 80

Sample Output 2

99

Out of the positive integers at most 100, all but 99 satisfy the condition.

Sample Input 3

1000000000000000000 1000000000

Sample Output 3

841103275147365677

Note that the answer may not fit into a 32-bit integer.

Problem Statement

For non-negative integers n and m, let us define the function f(n, m) as follows, using a positive integer K.

\displaystyle f(n, m) = \begin{cases} 0 & (n = 0) \\ n^K & (n \gt 0, m = 0) \\ f(n-1, m) + f(n, m-1) & (n \gt 0, m \gt 0) \end{cases}

Given N, M, and K, find f(N, M) modulo (10 ^ 9 + 7).

Constraints

• 0 \leq N \leq 10^{18}
• 0 \leq M \leq 30
• 1 \leq K \leq 2.5 \times 10^6
• All values in input are integers.

Sample Input 1

3 4 2

Sample Output 1

35

When K = 2, the values f(n, m) for n \leq 3, m \leq 4 are as follows.

Sample Input 2

0 1 2

Sample Output 2

0

Sample Input 3

1000000000000000000 30 123456

Sample Output 3

297085514