#E. Non-Intersecting Subpermutations

    Type: RemoteJudge 2000ms 512MiB

Non-Intersecting Subpermutations

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

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

The only line of the input contains two integers $n$ and $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$.

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

10 3
2 2
1337 42
71712
2
524933698

9月26日晚上集训比赛

Not Attended
Status
Done
Rule
IOI
Problem
6
Start at
2023-9-26 19:00
End at
2023-9-26 21:00
Duration
2 hour(s)
Host
Partic.
19