← 返回题目列表

Codeforces · 1989/E

E. 距离不同

中文机器翻译题面 查看原题

考虑一个由 $$$n$$$ 整数组成的数组 $$$a$$$,其中每个元素从 $$$1$$$ 到 $$$k$$$,并且从 $$$1$$$ 到 $$$k$$$ 的每个整数至少出现一次。

令数组 $$$b$$$ 构造如下:对于 $$$a$$$ 的第 $$$i$$$ 个元素,$$$b_i$$$ 是到 $$$a$$$ 中最近元素的距离,该元素不等于 $$$a_i$$$。换句话说,$$$b_i = \min \limits_{j \in [1, n], a_j \ne a_i} |i - j|$$$。

例如,如果 $$$a = [1, 1, 2, 3, 3, 3, 3, 1]$$$,则 $$$b = [2, 1, 1, 1, 2, 2, 1, 1]$$$。

计算如果考虑所有可能的数组 $$$a$$$ 可获得的不同数组 $$$b$$$ 的数量,并以 $$$998244353$$$ 为模打印它。

输入

输入的唯一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$2 \le k \le \min(n, 10)$$$)。

输出

打印一个整数 — 您可以获得的不同数组 $$$b$$$ 的数量,以 $$$998244353$$$ 为模。

示例

输入 #1

2 2

输出 #1

1

输入 #2

4 3

输出 #2

3

输入 #3

6 2

输出 #3

20

输入#4

6 5

输出#4

3

输入 #5

133 7

输出 #5

336975971