给你两个整数 $$$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