Problem Statement

Takahashi is distributing N balls to K persons.

If each person has to receive at least one ball, what is the maximum possible difference in the number of balls received between the person with the most balls and the person with the fewest balls?

Constraints

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

Sample Input 1

3 2

Sample Output 1

1

The only way to distribute three balls to two persons so that each of them receives at least one ball is to give one ball to one person and give two balls to the other person.

Thus, the maximum possible difference in the number of balls received is 1.

Sample Input 2

3 1

Sample Output 2

0

We have no choice but to give three balls to the only person, in which case the difference in the number of balls received is 0.

Sample Input 3

8 5

Sample Output 3

3

For example, if we give 1, 4, 1, 1, 1 balls to the five persons, the number of balls received between the person with the most balls and the person with the fewest balls would be 3, which is the maximum result.

Problem Statement

There are N balls in a two-dimensional plane. The i-th ball is at coordinates (x_i, y_i).

We will collect all of these balls, by choosing two integers p and q such that p \neq 0 or q \neq 0 and then repeating the following operation:

• Choose a ball remaining in the plane and collect it. Let (a, b) be the coordinates of this ball. If we collected a ball at coordinates (a - p, b - q) in the previous operation, the cost of this operation is 0. Otherwise, including when this is the first time to do this operation, the cost of this operation is 1.

Find the minimum total cost required to collect all the balls when we optimally choose p and q.

Constraints

• 1 \leq N \leq 50
• |x_i|, |y_i| \leq 10^9
• If i \neq j, x_i \neq x_j or y_i \neq y_j.
• All values in input are integers.

Sample Input 1

2
1 1
2 2

Sample Output 1

1

If we choose p = 1, q = 1, we can collect all the balls at a cost of 1 by collecting them in the order (1, 1), (2, 2).

Sample Input 2

3
1 4
4 6
7 8

Sample Output 2

1

If we choose p = -3, q = -2, we can collect all the balls at a cost of 1 by collecting them in the order (7, 8), (4, 6), (1, 4).

Sample Input 3

4
1 1
1 2
2 1
2 2

Sample Output 3

2

Problem Statement

There are N integers, A_1, A_2, ..., A_N, written on a blackboard.

We will repeat the following operation N-1 times so that we have only one integer on the blackboard.

• Choose two integers x and y on the blackboard and erase these two integers. Then, write a new integer x-y.

Find the maximum possible value of the final integer on the blackboard and a sequence of operations that maximizes the final integer.

Constraints

• 2 \leq N \leq 10^5
• -10^4 \leq A_i \leq 10^4
• All values in input are integers.

Sample Input 1

3
1 -1 2

Sample Output 1

4
-1 1
2 -2

If we choose x = -1 and y = 1 in the first operation, the set of integers written on the blackboard becomes (-2, 2).

Then, if we choose x = 2 and y = -2 in the second operation, the set of integers written on the blackboard becomes (4).

In this case, we have 4 as the final integer. We cannot end with a greater integer, so the answer is 4.

Sample Input 2

3
1 1 1

Sample Output 2

1
1 1
1 0

Problem Statement

The squirrel Chokudai has N acorns. One day, he decides to do some trades in multiple precious metal exchanges to make more acorns.

His plan is as follows:

1. Get out of the nest with N acorns in his hands.
2. Go to Exchange A and do some trades.
3. Go to Exchange B and do some trades.
4. Go to Exchange A and do some trades.
5. Go back to the nest.

In Exchange X (X = A, B), he can perform the following operations any integer number of times (possibly zero) in any order:

• Lose g_{X} acorns and gain 1 gram of gold.
• Gain g_{X} acorns and lose 1 gram of gold.
• Lose s_{X} acorns and gain 1 gram of silver.
• Gain s_{X} acorns and lose 1 gram of silver.
• Lose b_{X} acorns and gain 1 gram of bronze.
• Gain b_{X} acorns and lose 1 gram of bronze.

Naturally, he cannot perform an operation that would leave him with a negative amount of acorns, gold, silver, or bronze.

What is the maximum number of acorns that he can bring to the nest? Note that gold, silver, or bronze brought to the nest would be worthless because he is just a squirrel.

Constraints

• 1 \leq N \leq 5000
• 1 \leq g_{X} \leq 5000
• 1 \leq s_{X} \leq 5000
• 1 \leq b_{X} \leq 5000
• All values in input are integers.

Sample Input 1

23
1 1 1
2 1 1

Sample Output 1

46

He can bring 46 acorns to the nest, as follows:

• In Exchange A, trade 23 acorns for 23 grams of gold. {acorns, gold, silver, bronze}={ 0,23,0,0 }
• In Exchange B, trade 23 grams of gold for 46 acorns. {acorns, gold, silver, bronze}={ 46,0,0,0 }
• In Exchange A, trade nothing. {acorns, gold, silver, bronze}={ 46,0,0,0 }

He cannot have 47 or more acorns, so the answer is 46.

Problem Statement

There are N squares arranged in a row, numbered 1 to N from left to right. Takahashi will stack building blocks on these squares, on which there are no blocks yet.

He wants to stack blocks on the squares evenly, so he will repeat the following operation until there are H blocks on every square:

• Let M and m be the maximum and minimum numbers of blocks currently stacked on a square, respectively. Choose a square on which m blocks are stacked (if there are multiple such squares, choose any one of them), and add a positive number of blocks on that square so that there will be at least M and at most M + D blocks on that square.

Tell him how many ways there are to have H blocks on every square by repeating this operation. Since there can be extremely many ways, print the number modulo 10^9+7.

Constraints

• 2 \leq N \leq 10^6
• 1 \leq D \leq H \leq 10^6
• All values in input are integers.

Sample Input 1

2 2 1

Sample Output 1

6

The possible transitions of (the number of blocks on Square 1, the number of blocks on Square 2) are as follows:

• (0, 0) -> (0, 1) -> (1, 1) -> (1, 2) -> (2, 2)

• (0, 0) -> (0, 1) -> (1, 1) -> (2, 1) -> (2, 2)

• (0, 0) -> (0, 1) -> (2, 1) -> (2, 2)

• (0, 0) -> (1, 0) -> (1, 1) -> (1, 2) -> (2, 2)

• (0, 0) -> (1, 0) -> (1, 1) -> (2, 1) -> (2, 2)

• (0, 0) -> (1, 0) -> (1, 2) -> (2, 2)

Thus, there are six ways to have two blocks on every square.

Sample Input 2

2 30 15

Sample Output 2

94182806

Sample Input 3

31415 9265 3589

Sample Output 3

312069529

Be sure to print the number modulo 10^9+7.

Problem Statement

Diverta City is a new city consisting of N towns numbered 1, 2, ..., N.

The mayor Ringo is planning to connect every pair of two different towns with a bidirectional road. The length of each road is undecided.

A Hamiltonian path is a path that starts at one of the towns and visits each of the other towns exactly once. The reversal of a Hamiltonian path is considered the same as the original Hamiltonian path.

There are N! / 2 Hamiltonian paths. Ringo wants all these paths to have distinct total lengths (the sum of the lengths of the roads on a path), to make the city diverse.

Find one such set of the lengths of the roads, under the following conditions:

• The length of each road must be a positive integer.
• The maximum total length of a Hamiltonian path must be at most 10^{11}.

Constraints

• N is a integer between 2 and 10 (inclusive).

Sample Input 1

3

Sample Output 1

0 6 15
6 0 21
15 21 0

There are three Hamiltonian paths. The total lengths of these paths are as follows:

• 1 → 2 → 3: The total length is 6 + 21 = 27.
• 1 → 3 → 2: The total length is 15 + 21 = 36.
• 2 → 1 → 3: The total length is 6 + 15 = 21.

They are distinct, so the objective is met.

Sample Input 2

4

Sample Output 2

0 111 157 193
111 0 224 239
157 224 0 258
193 239 258 0

There are 12 Hamiltonian paths, with distinct total lengths.