配点 : 100 点
問題文
0 以上 M 的整数序列 满足以下条件的 A=(A_1,A_2,\ldots,A_N) 的数量为 序列为998244353 求余数。
- B_i=\operatorname{mex}(\lbrace A_i,A_{i+1},\ldots,A_{i+K-1}\rbrace) 当您创建 B=(B_1,B_2,\ldots,B_{N-K+1}) 时,B 严格单调递增。换句话说,B_1\lt B_2\lt\cdots\lt B_{N-K+1} 满意。
墨西哥的定义
非负整数有限集 对于 S , 非负整数\operatorname{mex}(S) 的 x\not\in S 定义为 x 的最小值。制約
- 1\leq N\leq 2\times 10^5
- 1\leq M\leq 2\times 10^5
- 1\leq K\leq N
入力
输入是按以下格式从标准输入给出的。
N M K
出力
条件已满足 如何选择 A 的数量 在一行上输出除以 998244353 后的余数。
入力例 1
3 1 2
出力例 1
2
(0,0,1) 和 (1,1,0) 的 2 满足条件。 请针对
入力例 2
4 4 1
出力例 2
0
入力例 3
271 828 182
出力例 3
125683497