CF1861E.Non-Intersecting Subpermutations

You are given two integers $n$ and $k$.

For an array of length $n$, let's define its cost as the maximum number of contiguous subarrays of this array that can be chosen so that:

• each element belongs to at most one subarray;
• the length of each subarray is exactly $k$;
• each subarray contains each integer from $1$ to $k$ exactly once.

For example, if $n = 10$, $k = 3$ and the array is $[1, 2, 1, 3, 2, 3, 2, 3, 1, 3]$, its cost is $2$ because, for example, we can choose the subarrays from the $2$-nd element to the $4$-th element and from the $7$-th element to the $9$-th element, and we can show that it's impossible to choose more than $2$ subarrays.

Calculate the sum of costs over all arrays of length $n$ consisting of integers from $1$ to $k$, and print it modulo $998244353$.

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

对于一个长度为 $n$ 的数组，我们定义其代价为：能够从中选出的、满足以下条件的互不重叠的连续子数组的最大个数：

• 每个元素至多属于一个子数组；
• 每个子数组的长度恰好为 $k$；
• 每个子数组恰好包含 $1$ 到 $k$ 中的每个整数各一次。

例如，若 $n = 10$，$k = 3$，数组为 $[1, 2, 1, 3, 2, 3, 2, 3, 1, 3]$，则其代价为 $2$。这是因为，例如我们可以选取从第 $2$ 个元素到第 $4$ 个元素的子数组（即 $[2,1,3]$）和从第 $7$ 个元素到第 $9$ 个元素的子数组（即 $[2,3,1]$）；并且可以证明无法选出超过 $2$ 个满足条件的子数组。

请计算所有由 $1$ 到 $k$ 中的整数组成的长度为 $n$ 的数组的代价之和，并将结果对 $998244353$ 取模后输出。

The only line of the input contains two integers $n$ and $k$ ($2 \le k \le n \le 4000$).

输入仅包含一行，其中有两个整数 $n$ 和 $k$（$2 \le k \le n \le 4000$）。

Print one integer — the sum of costs of all arrays of length $n$ consisting of integers from $1$ to $k$ taken modulo $998244353$.

输出一个整数——所有长度为 $n$、由 $1$ 到 $k$ 的整数组成的数组的成本之和，对 $998244353$ 取模。