問題文

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} を満たす。

制約

• 1\leq N\leq 2\times 10^5
• 1\leq M\leq 2\times 10^5
• 1\leq K\leq N

入力例 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