← 返回题目列表

Codeforces · 1861/E

E. 非相交子排列

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

给你两个整数 $$$n$$$ 和 $$$k$$$。

对于长度为 $$$n$$$ 的数组,我们将其成本定义为该数组可以选择的连续子数组的最大数量,以便:

- 每个元素最多属于一个子数组;
- 每个子数组的长度正好是$$$k$$$;
- 每个子数组只包含从 $$$1$$$ 到 $$$k$$$ 的每个整数一次。

例如,如果 $$$n = 10$$$,$$$k = 3$$$ 并且数组为 $$$[1, 2, 1, 3, 2, 3, 2, 3, 1, 3]$$$,则其成本为 $$$2$$$,因为例如,我们可以选择从 $$$2$$$-nd 元素到第第 $$$4$$$ 个元素以及从第 $$$7$$$ 个元素到第 $$$9$$$ 个元素,我们可以证明不可能选择超过 $$$2$$$ 的子数组。

计算所有长度为 $$$n$$$ 的数组(由 $$$1$$$ 到 $$$k$$$ 之间的整数组成的成本总和,并以 $$$998244353$$$ 为模进行打印。

输入

输入的唯一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le k \le n \le 4000$$$)。

输出

打印一个整数 — 所有长度为 $$$n$$$ 的数组的成本总和,由从 $$$1$$$ 到 $$$k$$$ 的整数组成,以 $$$998244353$$$ 为模。

示例

输入 #1

10 3

输出 #1

71712

输入 #2

2 2

输出 #2

2

输入 #3

1337 42

输出 #3

524933698