310623: CF1861E. Non-Intersecting Subpermutations

E. Non-Intersecting Subpermutationstime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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$.

Input

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

Output

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

ExamplesInput

10 3

Output

71712

Input

2 2

Output

2

Input

1337 42

Output

524933698

题目大意：
这是一个关于子排列的问题。给定两个整数n和k，你需要计算所有长度为n，由1到k的整数组成的数组的成本之和，并对998244353取模。

数组成本的定义是：从数组中可以选择的，长度恰好为k的，互不重叠的连续子数组的最大数量，且每个子数组包含从1到k的每个整数恰好一次。

输入输出数据格式：
输入：
- 一行两个整数n和k（2≤k≤n≤4000）

输出：
- 一个整数，表示所有长度为n，由1到k的整数组成的数组的成本之和，对998244353取模后的结果。

示例：
输入：
10 3
输出：
71712

输入：
2 2
输出：
2

输入：
1337 42
输出：
524933698题目大意： 这是一个关于子排列的问题。给定两个整数n和k，你需要计算所有长度为n，由1到k的整数组成的数组的成本之和，并对998244353取模。 数组成本的定义是：从数组中可以选择的，长度恰好为k的，互不重叠的连续子数组的最大数量，且每个子数组包含从1到k的每个整数恰好一次。 输入输出数据格式： 输入： - 一行两个整数n和k（2≤k≤n≤4000） 输出： - 一个整数，表示所有长度为n，由1到k的整数组成的数组的成本之和，对998244353取模后的结果。 示例： 输入： 10 3 输出： 71712 输入： 2 2 输出： 2 输入： 1337 42 输出： 524933698