CF BUDDY
← Problems·

1989E · Distance to Different

2300 · combinatorics, dp, math

Problem: Consider an array aa of nn integers, where every element is from 11 to kk, and every integer from 11 to kk appears at least once.

Let the array bb be constructed as follows: for the ii-th element of aa, bib_i is the distance to the closest element in aa which is not equal to aia_i. In other words, bi=minj[1,n],ajaiijb_i = \min \limits_{j \in [1, n], a_j \ne a_i} |i - j|.

For example, if a=[1,1,2,3,3,3,3,1]a = [1, 1, 2, 3, 3, 3, 3, 1], then b=[2,1,1,1,2,2,1,1]b = [2, 1, 1, 1, 2, 2, 1, 1].

Calculate the number of different arrays bb you can obtain if you consider all possible arrays aa, and print it modulo 998244353998244353.

Input Format: The only line of the input contains two integers nn and kk (2n21052 \le n \le 2 \cdot 10^5; 2kmin(n,10)2 \le k \le \min(n, 10)).

Output Format: Print one integer — the number of different arrays bb you can obtain, taken modulo 998244353998244353.

Sample Cases

Case 1

Input

2 2

Output

1

Case 2

Input

4 3

Output

3

Case 3

Input

6 2

Output

20

Case 4

Input

6 5

Output

3

Case 5

Input

133 7

Output

336975971

Similar problems

00:00:00
Loading editor…
Welcome! I'm your coding tutor for this problem. Use the chips below to reveal stored hints or get AI feedback on your code. I'll guide you step by step — never giving away the solution.

Sign in to unlock AI tutor feedback