Problem Statement

We will hand out a total of K cards to N people numbered 1, 2, \ldots, N.

Beginning with Person A, we will give the cards one by one to the people in this order: A, A+1, A+2, \ldots, N, 1, 2, \ldots. Who will get the last card?

Formally, after Person x(1 \leq x < N) gets a card, Person x+1 will get a card. After Person N gets a card, Person 1 gets a card.

Constraints

• 1 \leq N,K \leq 1000
• 1 \leq A \leq N
• All values in input are integers.

Sample Input 1

3 3 2

Sample Output 1

1

The cards are given to Person 2, 3, 1 in this order.

Sample Input 2

1 100 1

Sample Output 2

1

Sample Input 3

3 14 2

Sample Output 3

3

Problem Statement

There are N people numbered 1 to N.

Person i guessed the building area of KEYENCE headquarters building to be S_i square meters.

The shape of KEYENCE headquarters building is shown below, where a and b are some positive integers.
That is, the building area of the building can be represented as 4ab+3a+3b.

Based on just this information, how many of the N people are guaranteed to be wrong in their guesses?

Constraints

• 1 \leq N \leq 20
• 1 \leq S_i \leq 1000
• All values in input are integers.

Sample Input 1

3
10 20 39

Sample Output 1

1

The area would be 10 square meters if a=1,b=1, and 39 square meters if a=2,b=3.

However, no pair of positive integers a and b would make the area 20 square meters.

Thus, we can only be sure that Person 2 guessed wrong.

Sample Input 2

5
666 777 888 777 666

Sample Output 2

3

Problem Statement

You are given a positive integer N.

Find the number of triples of positive integers (A, B, C) such that A\leq B\leq C and ABC\leq N.

The Constraints guarantee that the answer is less than 2^{63}.

Constraints

• 1 \leq N \leq 10^{11}
• N is an integer.

Sample Input 1

4

Sample Output 1

5

There are five such triples: (1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,2,2).

Sample Input 2

100

Sample Output 2

323

Sample Input 3

100000000000

Sample Output 3

5745290566750

Problem Statement

KEYENCE has N departments, where A_i employees belong to the i-th department (1 \leq i \leq N). No employee belongs to multiple departments.

The company is planning cross-departmental projects. Each project will be composed of exactly K employees chosen from K distinct departments.

At most how many projects can be made? No employee can participate in multiple projects.

Constraints

• 1 \leq K \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^{12}
• All values in input are integers.

Sample Input 1

3 3
2 3 4

Sample Output 1

2

There can be two projects, each composed of three employees from distinct departments.

Sample Input 2

4 2
1 1 3 4

Sample Output 2

4

Sample Input 3

4 3
1 1 3 4

Sample Output 3

2

Problem Statement

Given is a string S consisting of K, E, Y.

How many strings are there that can be obtained with at most K swaps of two adjacent characters in S?

Constraints

• 2 \leq |S| \leq 30
• 0 \leq K \leq 10^9
• S consists of K, E, Y.

Sample Input 1

KEY
1

Sample Output 1

3

With at most one swap, there are three strings that can be obtained: KEY, EKY, KYE.

Sample Input 2

KKEE
2

Sample Output 2

4

With at most two swaps, there are four strings that can be obtained: KKEE, KEKE, EKKE, KEEK.

Sample Input 3

KKEEYY
1000000000

Sample Output 3

90

Problem Statement

We have a grid with H horizontal rows and W vertical columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left. (i, j) contains an integer A_{i,j}.

Takahashi will depart (1, 1) and repeatedly move one square right or down until reaching (H, W). It is not allowed to exit the grid.

The cost of this travel is defined as:

the sum of the K greatest integers among the integers written on the H+W-1 squares traversed.

Find the minimum possible cost.

Constraints

• 1 \leq H,W \leq 30
• 1 \leq K < H+W
• 1 \leq A_{i,j} \leq 10^9
• All values in input are integers.

Sample Input 1

1 3 2
3 4 5

Sample Output 1

9

There is only one way to travel, where the traversed squares contain the integers 5, 4, 3 from largest to smallest, so we print 9(=5+4).

Sample Input 2

2 2 1
3 2
4 3

Sample Output 2

3

The minimum cost is achieved by traversing (1,1), (1,2), (2,2) in this order.

Sample Input 3

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

Sample Output 3

21

Problem Statement

Find the number, modulo 998244353, of positive divisors of a binomial coefficient \displaystyle \binom{N}{K}.

Constraints

• 1 \leq N \leq 10^{12}
• 0 \leq K \leq \min(10^6,N)
• All values in input are integers.

Sample Input 1

5 2

Sample Output 1

4

We have \displaystyle \binom{5}{2}=10, which has four positive divisors: 1,2,5,10.

Sample Input 2

103 3

Sample Output 2

8

We have \displaystyle \binom{103}{3}=176851, which has eight positive divisors.

Sample Input 3

1000000000000 1000000

Sample Output 3

110520107

Problem Statement

We have a grid with 3 horizontal rows and 3 vertical columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left. (i, j) contains A_{i,j} cans of cat food.

Snuke is now on (1,1). He will repeat the following action.

• Consume one can on the square he is on, and move up, down, left, or right to an adjacent square.

When there is no more can on the square he is on, he will end this process.

Is it possible that all of the conditions below are satisfied at the end of the process? If it is possible, show one sequence of actions that make it happen.

• Snuke is at (1,1).
• There is no more can on every square.

Constraints

• 1 \leq A_{i,j} \leq 100
• All values in input are integers.

Sample Input 1

1 1 1
1 1 1
1 2 1

Sample Output 1

DDRUDRUULL

Note that Snuke must be back on (1, 1) in the end.

There are also other correct outputs, such as RRDDLUDLUU.

Sample Input 2

2 4 2
2 1 1
1 1 2

Sample Output 2

NO

It is impossible to achieve the objective, so print NO.

Sample Input 3

2 2 3
2 1 2
1 3 2

Sample Output 3

DUDDRUDRLRUULRDULL