[R66E]安检 - 代码源竞赛平台

时空限制

1S/512M

题目描述

有 $n$ 个不同的人等待安检，有 $m$ 个不同的安检口。

所有人会确定一个总安检顺序，并按该顺序被划分成若干个连续、非空的批次。每一批的人数不能超过 $m$，且需要选择与该批人数相同数量的不同安检口。这里只记录每一批选择的安检口集合，不区分每个人具体对应哪个安检口。

两个方案不同，当且仅当总安检顺序、批次划分或任意一批选择的安检口集合中至少有一项不同。

现在 apiadu 作为领导，想知道方案数对 $998244353$ 取模后的结果。

格式

输入格式

第一行包含两个整数 $n$ 和 $m$。具体含义见题目描述。

输出格式

一个整数表示答案对 $998244353$ 取模后的值。

样例

样例输入 #1

2 3

样例输出 #1

24

样例解释 #1

两个人的总安检顺序共有 $2$ 种。对于每一种总安检顺序：

• 如果两个人属于同一批，需要从 $3$ 个安检口中选择 $2$ 个，共有 $3$ 种方案；
• 如果两个人分别属于两个批次，每一批都可以从 $3$ 个安检口中选择 $1$ 个，共有 $3 \times 3 = 9$ 种方案。

因此答案为 $2 \times (3 + 9) = 24$。

样例输入 #2

4 4

样例输出 #2

14712

样例输入 #3

3932 581438

样例输出 #3

241145307

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$
$1$	$20$	$10$
$2$	$80$	$5000$

对于 $100\%$ 的数据，满足 $1 \le n \le 5000$，$1 \le m \le 10^6$。