問題文

長さ $N$ かつ総和 $M$ である非負整数列 $A=(A_1,A_2,\\dots,A_N)$ のうち、以下の条件を満たすものの個数を $998244353$ で割ったあまりを求めてください。

• 以下の操作のうちどちらかを選んで行うことを繰り返して、$A$ の全ての要素を $0$ にすることが出来る。
  • $1 \\le i \\le N$ を満たす整数 $i$ を選び、$A_i$ を $K$ 減らす。
  • $1 \\le i \\le N-K+1$ を満たす整数 $i$ を選び、$A_i,A_{i+1},\\dots,A_{i+K-1}$ を $1$ ずつ減らす。

制約

• $1 \\le K \\le N \\le 2000$
• $1 \\le M \\le 10^{18}$

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $K$

出力

答えを出力せよ。

入力例 1

3 2 2

出力例 1

5

条件を満たす数列は、以下の $5$ 個です。

• $(1,1,0)$
• $(0,1,1)$
• $(2,0,0)$
• $(0,2,0)$
• $(0,0,2)$

例えば、$A=(0,1,1)$ の場合は以下のように操作をすることで全ての要素を $0$ にすることが出来ます。

• $2$ 個目の操作を行う。$i$ として $2$ を選ぶ。$A_2,A_3$ を $1$ ずつ減らす。$A=(0,0,0)$ となる。

入力例 2

100 998244353 100

出力例 2

0

条件を満たす数列が存在しない場合もあります。

入力例 3

2000 545782618661124208 533

出力例 3

908877889