Problem Statement

The consumption tax rate in the Republic of ARC is t percent, where t is a positive integer.

There is a shop called Seisu-ya (integer shop) there. It sells each positive integer A for A yen (Japanese currency) excluding tax, that is, \left\lfloor\frac{100+t}{100}A\right\rfloor yen including tax. Here, \lfloor x\rfloor denotes the largest integer not greater than x for a real number x.

Although Seisu-ya sells every positive integer, there are some positive integer values that cannot be the tax-included price of an integer. Among those values, find the N-th smallest value.

Constraints

• 1\leq t\leq 50
• 1\leq N\leq 10^{9}

Sample Input 1

10 1

Sample Output 1

10

In this sample, the consumption tax rate is 10 percent.

• The integer 9 is sold for \left\lfloor \frac{110}{100}\times 9\right\rfloor = \lfloor 9.9\rfloor = 9 yen including tax.
• The integer 10 is sold for \left\lfloor \frac{110}{100}\times 10\right\rfloor = \lfloor 11\rfloor = 11 yen including tax.

From above, we can see that 10 is not the tax-included price of any integer, and this is the minimum such value.

Sample Input 2

3 5

Sample Output 2

171

If the consumption tax rate is 3 percent, the smallest values that cannot be the tax-included price of an integer are 34, 68, 102, 137, 171, \ldots

Sample Input 3

1 1000000000

Sample Output 3

100999999999

Problem Statement

The Republic of ARC has N citizens, all of whom play competitive programming. Each citizen is given a dan (grade) which is 1, 2, \ldots, or K, according to their skill.

A national census has revealed that there are exactly A_i citizens with dan i. To make this data easier to understand, the king has decided to describe the country as if it were a village of M people.

Set the number of people with dan i in the village, B_i, so that \max_i\left|\frac{B_i}{M} - \frac{A_i}{N}\right| is minimized, while satisfying the following:

• each B_i is a non-negative integer, satisfying \sum_{i=1}^K B_i = M.

Print one such way to set B = (B_1, B_2, \ldots, B_K).

Constraints

• 1\leq K\leq 10^5
• 1\leq N, M\leq 10^9
• Each A_i is a non-negative integer satisfying \sum_{i=1}^K A_i = N.

Sample Input 1

3 7 20
1 2 4

Sample Output 1

3 6 11

In this output, we have \max_i\left|\frac{B_i}{M} - \frac{A_i}{N}\right| = \max\left(\left|\frac{3}{20}-\frac{1}{7}\right|, \left|\frac{6}{20}-\frac{2}{7}\right|, \left|\frac{11}{20}-\frac{4}{7}\right|\right) = \max\left(\frac{1}{140}, \frac{1}{70}, \frac{3}{140}\right) = \frac{3}{140}.

Sample Input 2

3 3 100
1 1 1

Sample Output 2

34 33 33

Note that B_1 = B_2 = B_3 = 33 does not satisfy the requirement, since the sum must be M = 100.

In this sample, other than 34 33 33, printing 33 34 33 or 33 33 34 will also be accepted.

Sample Input 3

6 10006 10
10000 3 2 1 0 0

Sample Output 3

10 0 0 0 0 0

Sample Input 4

7 78314 1000
53515 10620 7271 3817 1910 956 225

Sample Output 4

683 136 93 49 24 12 3

Problem Statement

Given is a positive integer N. Print an integer sequence A = (A_1, A_2, \ldots, A_N) satisfying all of the following:

• 1\leq A_i\leq 10000;
• A_i\neq A_j and \gcd(A_i, A_j) > 1 for i\neq j;
• \gcd(A_1, A_2, \ldots, A_N) = 1.

We can prove that, under the Constraints of this problem, such an integer sequence always exists.

Constraints

• 3\leq N\leq 2500

Sample Input 1

4

Sample Output 1

84 60 105 70

All of the conditions are satisfied, since we have:

• \gcd(84,60) = 12
• \gcd(84,105) = 21
• \gcd(84,70) = 14
• \gcd(60,105) = 15
• \gcd(60,70) = 10
• \gcd(105,70) = 35
• \gcd(84,60,105,70) = 1

Problem Statement

Given are a prime number P and positive integers a and b. Determine whether there is a sequence of P integers, A = (A_1, A_2, \ldots, A_P), satisfying all of the conditions below, and print one such sequence if it exists.

• 1\leq A_i\leq P - 1.
• A_1 = A_P = 1.
• (A_1, A_2, \ldots, A_{P-1}) is a permutation of (1, 2, \ldots, P-1).
• For every 2\leq i\leq P, at least one of the following holds.
  • A_{i} \equiv aA_{i-1}\pmod{P}
  • A_{i-1} \equiv aA_{i}\pmod{P}
  • A_{i} \equiv bA_{i-1}\pmod{P}
  • A_{i-1} \equiv bA_{i}\pmod{P}

Constraints

• 2\leq P\leq 10^5
• P is a prime.
• 1\leq a, b \leq P - 1

Sample Input 1

13 4 5

Sample Output 1

Yes
1 5 11 3 12 9 7 4 6 8 2 10 1

This sequence satisfies the conditions, since we have the following modulo P = 13:

• A_2\equiv 5A_1
• A_2\equiv 4A_3
• \vdots
• A_{13}\equiv 4A_{12}

Sample Input 2

13 1 2

Sample Output 2

Yes
1 2 4 8 3 6 12 11 9 5 10 7 1

Sample Input 3

13 9 3

Sample Output 3

No

Sample Input 4

13 1 1

Sample Output 4

No

Problem Statement

Let us consider the problem below for a permutation P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N), and denote the answer by f(P).

We have an (N+2)\times (N+2) grid, where the rows are numbered 0, 1, \ldots, N+1 from top to bottom and the columns are numbered 0, 1, \ldots, N+1 from left to right. Let (i,j) denote the square at the i-th row and j-th column.

Consider paths from (0, 0) to (N+1, N+1) where we repeatedly move one square right or one square down. However, for each 1\leq i\leq N, we must not visit the square (i, P_i). How many such paths are there?

You are given a positive integer N and an integer sequence A = (A_1, A_2, \ldots, A_N), where each A_i is -1 or an integer between 1 and N (inclusive).

Consider all permutations P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N) satisfying A_i\neq -1 \implies P_i = A_i. Find the sum of f(P) over all such P, modulo 998244353.

Constraints

• 1\leq N\leq 200
• A_i = -1 or 1\leq A_i\leq N.
• A_i\neq A_j if A_i\neq -1 and A_j\neq -1, for i\neq j.

Sample Input 1

4
1 -1 4 -1

Sample Output 1

41

We want to find the sum of f(P) over two permutations P = (1,2,4,3) and P = (1,3,4,2). The figure below shows the impassable squares for each of them, where . and # represent a passable and impassable square, respectively.

  ......         ......
  .#....         .#....
  ..#...         ...#..
  ....#.         ....#.
  ...#..         ..#...
  ......         ......
P=(1,2,4,3)    P=(1,3,4,2)

• For P = (1,2,4,3), we have f(P) = 18.
• For P = (1,3,4,2), we have f(P) = 23.

The answer is the sum of them: 41.

Sample Input 2

4
4 3 2 1

Sample Output 2

2

In this sample, we want to compute f(P) for just one permutation P = (4,3,2,1).

Sample Input 3

3
-1 -1 -1

Sample Output 3

48

• For P = (1,2,3), we have f(P) = 10.
• For P = (1,3,2), we have f(P) = 6.
• For P = (2,1,3), we have f(P) = 6.
• For P = (2,3,1), we have f(P) = 12.
• For P = (3,1,2), we have f(P) = 12.
• For P = (3,2,1), we have f(P) = 2.

The answer is the sum of them: 48.

Problem Statement

Given is a positive integer M and a sequence of N integers: A = (A_1,A_2,\ldots,A_N). Find the number, modulo 998244353, of sequences of N+1 integers, X = (X_1,X_2, \ldots, X_{N+1}), satisfying all of the following conditions:

• 1\leq X_i\leq M (1\leq i\leq N+1)
• A_iX_i\leq X_{i+1} (1\leq i\leq N)

Constraints

• 1\leq N\leq 1000
• 1\leq M\leq 10^{18}
• 1\leq A_i\leq 10^9
• \prod_{i=1}^N A_i \leq M

Sample Input 1

2 10
2 3

Sample Output 1

7

Seven sequences below satisfy the conditions.

• (1, 2, 6), (1,2,7), (1,2,8), (1,2,9), (1,2,10), (1,3,9), (1,3,10)

Sample Input 2

2 10
3 2

Sample Output 2

9

Nine sequences below satisfy the conditions.

• (1, 3, 6), (1, 3, 7), (1, 3, 8), (1, 3, 9), (1, 3, 10), (1, 4, 8), (1, 4, 9), (1, 4, 10), (1, 5, 10)

Sample Input 3

7 1000
1 2 3 4 3 2 1

Sample Output 3

225650129

Sample Input 4

5 1000000000000000000
1 1 1 1 1

Sample Output 4

307835847