配点 : $700$ 点

問題文

長さ $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 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$

出力

答えを出力せよ。

3 2 2

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)$ となる。

100 998244353 100

0

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

2000 545782618661124208 533

908877889