Problem Statement

Given an integer N, find the number of integers X that satisfy all of the following conditions, modulo 998244353.

• X is an N-digit positive integer.
• Let X_1,X_2,\dots,X_N be the digits of X from top to bottom. They satisfy all of the following:
  • 1 \le X_i \le 9 for all integers 1 \le i \le N;
  • |X_i-X_{i+1}| \le 1 for all integers 1 \le i \le N-1.

Constraints

• N is an integer.
• 2 \le N \le 10^6

Sample Input 1

4

Sample Output 1

203

Some of the 4-digit integers satisfying the conditions are 1111,1234,7878,6545.

Sample Input 2

2

Sample Output 2

25

Sample Input 3

1000000

Sample Output 3

248860093

Be sure to find the count modulo 998244353.

Problem Statement

In a parallel universe, AtCoder holds AtCoder Big Contest, where 10^{16} problems are given at once.
The IDs of the problems are as follows, from the 1-st problem in order: A, B, ..., Z, AA, AB, ..., ZZ, AAA, ...

In other words, the IDs are given in the following order:

• the strings of length 1 consisting of uppercase English letters, in lexicographical order;
• the strings of length 2 consisting of uppercase English letters, in lexicographical order;
• the strings of length 3 consisting of uppercase English letters, in lexicographical order;
• ...

Given a string S that is an ID of a problem given in this contest, find the index of the problem. (See also Samples.)

Constraints

• S is a valid ID of a problem given in AtCoder Big Contest.

Sample Input 1

AB

Sample Output 1

28

The problem whose ID is AB is the 28-th problem of AtCoder Big Contest, so 28 should be printed.

Sample Input 2

C

Sample Output 2

3

The problem whose ID is C is the 3-rd problem of AtCoder Big Contest, so 3 should be printed.

Sample Input 3

BRUTMHYHIIZP

Sample Output 3

10000000000000000

The problem whose ID is BRUTMHYHIIZP is the 10^{16}-th (last) problem of AtCoder Big Contest, so 10^{16} should be printed as an integer.

Problem Statement

Given are a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) and a positive integer K.

For each i=K,K+1,\ldots,N, find the following.

• The K-th greatest value among the first i terms of P.

Constraints

• 1 \leq K \leq N \leq 5 \times 10^5
• (P_1,P_2,\ldots,P_N) is a permutation of (1,2,\ldots,N).
• All values in input are integers.

Sample Input 1

3 2
1 2 3

Sample Output 1

1
2

• The (K=) 2-nd greatest value among the first 2 terms of P, (P_1,P_2)=(1,2), is 1.
• The (K=) 2-nd greatest value among the first 3 terms of P, (P_1,P_2,P_3)=(1,2,3), is 2.

Sample Input 2

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

Sample Output 2

2
3
3
5
6
7
7

Problem Statement

You are given N points in the coordinate plane. For each 1\leq i\leq N, the i-th point is at the coordinates (X_i, Y_i).

Find the number of lines in the plane that pass K or more of the N points.
If there are infinitely many such lines, print Infinity.

Constraints

• 1 \leq K \leq N \leq 300
• \lvert X_i \rvert, \lvert Y_i \rvert \leq 10^9
• X_i\neq X_j or Y_i\neq Y_j, if i\neq j.
• All values in input are integers.

Sample Input 1

5 2
0 0
1 0
0 1
-1 0
0 -1

Sample Output 1

6

The six lines x=0, y=0, y=x\pm 1, and y=-x\pm 1 satisfy the requirement.
For example, x=0 passes the first, third, and fifth points.

Thus, 6 should be printed.

Sample Input 2

1 1
0 0

Sample Output 2

Infinity

Infinitely many lines pass the origin.

Thus, Infinity should be printed.

Problem Statement

In the Kingdom of Takahashi, N citizens numbered 1 to N took an examination of competitive programming.
There were two tests, and Citizen i ranked P_i-th in the first test and Q_i-th in the second test.
There were no ties in either test. That is, each of the sequences P and Q is a permutation of (1, 2, ..., N).

Iroha, the president of the kingdom, is going to select K citizens for the national team at the coming world championship of competitive programming.
The members of the national team must be selected so that the following is satisfied.

• There should not be a pair of citizens (x, y) where Citizen x is selected and Citizen y is not selected such that P_x > P_y and Q_x > Q_y.
  • In other words, if Citizen y got a rank smaller than that of Citizen x in both tests, it is not allowed to select Citizen x while not selecting Citizen y.

To begin with, Iroha wants to know the number of ways to select citizens for the national team that satisfy the condition above. Find it to help her.
Since this number can be enormous, print it modulo 998244353.

Constraints

• All values in input are integers.
• 1 \le N \le 300
• 1 \le K \le N
• Each of P and Q is a permutation of (1,2,...,N).

Sample Input 1

4 2
2 4 3 1
2 1 4 3

Sample Output 1

3

• It is fine to select Citizen 1 and Citizen 2 for the team.
• If Citizen 1 and Citizen 3 are selected, Citizen 4 ranked higher than Citizen 3 did in both tests, so the pair (x,y)=(3,4) would violate the condition in the Problem Statement.
• It is fine to select Citizen 1 and Citizen 4.
• If Citizen 2 and Citizen 3 are selected, the pair (x,y)=(3,1) would violate the condition.
• It is fine to select Citizen 2 and Citizen 4.
• If Citizen 3 and Citizen 4 are selected, the pair (x,y)=(3,1) would violate the condition.

The final answer is 3.

Sample Input 2

33 16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

Sample Output 2

168558757

All \binom{33}{16} = 1166803110 ways of selecting 16 from the 33 citizens satisfy the requirement.
Therefore, we should print 1166803110 modulo 998244353, that is, 168558757.

Sample Input 3

15 7
4 9 7 5 6 13 2 11 3 1 12 14 15 10 8
4 14 9 12 7 15 1 2 8 11 3 5 13 6 10

Sample Output 3

23