Problem Statement

Find the maximum possible sum of the digits (in base 10) of a positive integer not greater than N.

Constraints

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

Sample Input 1

100

Sample Output 1

18

For example, the sum of the digits in 99 is 18, which turns out to be the maximum value.

Sample Input 2

9995

Sample Output 2

35

For example, the sum of the digits in 9989 is 35, which turns out to be the maximum value.

Sample Input 3

3141592653589793

Sample Output 3

137

Problem Statement

There are N holes in a two-dimensional plane. The coordinates of the i-th hole are (x_i,y_i).

Let R=10^{10^{10^{10}}}. Ringo performs the following operation:

• Randomly choose a point from the interior of a circle of radius R centered at the origin, and put Snuke there. Snuke will move to the hole with the smallest Euclidean distance from the point, and fall into that hole. If there are multiple such holes, the hole with the smallest index will be chosen.

For every i (1 \leq i \leq N), find the probability that Snuke falls into the i-th hole.

Here, the operation of randomly choosing a point from the interior of a circle of radius R is defined as follows:

• Pick two real numbers x and y independently according to uniform distribution on [-R,R].
• If x^2+y^2\leq R^2, the point (x,y) is chosen. Otherwise, repeat picking the real numbers x,y until the condition is met.

Constraints

• 2 \leq N \leq 100
• |x_i|,|y_i| \leq 10^6(1\leq i\leq N)
• All given points are pairwise distinct.
• All input values are integers.

Sample Input 1

2
0 0
1 1

Sample Output 1

0.5
0.5

If Ringo put Snuke in the region x+y\leq 1, Snuke will fall into the first hole. The probability of this happening is very close to 0.5. Otherwise, Snuke will fall into the second hole, the probability of which happening is also very close to 0.5.

Sample Input 2

5
0 0
2 8
4 5
2 6
3 10

Sample Output 2

0.43160120892732328768
0.03480224363653196956
0.13880483535586193855
0.00000000000000000000
0.39479171208028279727

Problem Statement

Takahashi has an N \times M grid, with N horizontal rows and M vertical columns. Determine if we can place A 1 \times 2 tiles (1 vertical, 2 horizontal) and B 2 \times 1 tiles (2 vertical, 1 horizontal) satisfying the following conditions, and construct one arrangement of the tiles if it is possible:

• All the tiles must be placed on the grid.
• Tiles must not stick out of the grid, and no two different tiles may intersect.
• Neither the grid nor the tiles may be rotated.
• Every tile completely covers exactly two squares.

Constraints

• 1 \leq N,M \leq 1000
• 0 \leq A,B \leq 500000
• N, M, A and B are integers.

Sample Input 1

3 4 4 2

Sample Output 1

YES
<><>
^<>^
v<>v

This is one example of a way to place four 1 \times 2 tiles and three 2 \times 1 tiles on a 3 \times 4 grid.

Sample Input 2

4 5 5 3

Sample Output 2

YES
<>..^
^.<>v
v<>.^
<><>v

Sample Input 3

7 9 20 20

Sample Output 3

NO

Problem Statement

Takahashi has decided to give a string to his mother.

The value of a string T is the length of the longest common subsequence of T and T', where T' is the string obtained by reversing T. That is, the value is the longest length of the following two strings that are equal: a subsequence of T (possibly non-contiguous), and a subsequence of T' (possibly non-contiguous).

Takahashi has a string S. He wants to give her mother a string of the highest possible value, so he would like to change at most K characters in S to any other characters in order to obtain a string of the highest possible value. Find the highest possible value achievable.

Constraints

• 1 \leq |S| \leq 300
• 0 \leq K \leq |S|
• S consists of lowercase English letters.
• K is an integer.

Sample Input 1

abcabcabc
1

Sample Output 1

7

Changing the first character to c results in cbcabcabc. Let this tring be T, then one longest common subsequence of T and T' is cbabcbc, whose length is 7.

Sample Input 2

atcodergrandcontest
3

Sample Output 2

15

Problem Statement

In Republic of AtCoder, Snuke Chameleons (Family: Chamaeleonidae, Genus: Bartaberia) are very popular pets. Ringo keeps N Snuke Chameleons in a cage.

A Snuke Chameleon that has not eaten anything is blue. It changes its color according to the following rules:

• A Snuke Chameleon that is blue will change its color to red when the number of red balls it has eaten becomes strictly larger than the number of blue balls it has eaten.
• A Snuke Chameleon that is red will change its color to blue when the number of blue balls it has eaten becomes strictly larger than the number of red balls it has eaten.

Initially, every Snuke Chameleon had not eaten anything. Ringo fed them by repeating the following process K times:

• Grab either a red ball or a blue ball.
• Throw that ball into the cage. Then, one of the chameleons eats it.

After Ringo threw in K balls, all the chameleons were red. We are interested in the possible ways Ringo could have thrown in K balls. How many such ways are there? Find the count modulo 998244353. Here, two ways to throw in balls are considered different when there exists i such that the color of the ball that are thrown in the i-th throw is different.

Constraints

• 1 \leq N,K \leq 5 \times 10^5
• N and K are integers.

Sample Input 1

2 4

Sample Output 1

7

We will use R to represent a red ball, and B to represent a blue ball. There are seven ways to throw in balls that satisfy the condition: BRRR, RBRB, RBRR, RRBB, RRBR, RRRB and RRRR.

Sample Input 2

3 7

Sample Output 2

57

Sample Input 3

8 3

Sample Output 3

0

Sample Input 4

8 10

Sample Output 4

46

Sample Input 5

123456 234567

Sample Output 5

857617983

Problem Statement

We have an N \times M grid. The square at the i-th row and j-th column will be denoted as (i,j). Particularly, the top-left square will be denoted as (1,1), and the bottom-right square will be denoted as (N,M). Takahashi painted some of the squares (possibly zero) black, and painted the other squares white.

We will define an integer sequence A of length N, and two integer sequences B and C of length M each, as follows:

• A_i(1\leq i\leq N) is the minimum j such that (i,j) is painted black, or M+1 if it does not exist.
• B_i(1\leq i\leq M) is the minimum k such that (k,i) is painted black, or N+1 if it does not exist.
• C_i(1\leq i\leq M) is the maximum k such that (k,i) is painted black, or 0 if it does not exist.

How many triples (A,B,C) can occur? Find the count modulo 998244353.

Notice

In this problem, the length of your source code must be at most 20000 B. Note that we will invalidate submissions that exceed the maximum length.

Input

Input is given from Standard Input in the following format:

N M

Output

Print the number of triples (A,B,C), modulo 998244353.

Sample Input 1

2 3

Sample Output 1

64

Since N=2, given B_i and C_i, we can uniquely determine the arrangement of black squares in each column. For each i, there are four possible pairs (B_i,C_i): (1,1), (1,2), (2,2) and (3,0). Thus, the answer is 4^M=64.

Sample Input 2

4 3

Sample Output 2

2588

Sample Input 3

17 13

Sample Output 3

229876268

Sample Input 4

5000 100

Sample Output 4

57613837