← 返回题目列表

AtCoder · pakencamp_2023_day3_e

E. 墨西哥

中文机器翻译题面 查看原题

配点 : 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