不相交子排列

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

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

对于一个长度为 $n$、元素均在 $1$ 到 $k$ 之间的数组，定义它的代价为能够选出的连续子数组的最大数量，并满足：

• 每个数组元素至多属于一个被选子数组；
• 每个被选子数组的长度恰为 $k$；
• 每个被选子数组恰好包含 $1,2,\ldots,k$ 各一次。

求所有 $k^n$ 个可能数组的代价之和。答案对 $998244353$ 取模。

输入格式

输入一行两个整数 $n,k$。

输出格式

输出一个整数，表示所有数组的代价之和对 $998244353$ 取模后的结果。

样例输入 1

10 3

样例输出 1

71712

样例输入 2

2 2

样例输出 2

2

样例输入 3

1337 42

样例输出 3

524933698

数据范围

对于所有数据，$2\le k\le n\le 4000$。

所有测试点均为独立计分点。