AT_arc160_d [ARC160D] Mahjong

[problemUrl]: https://atcoder.jp/contests/arc160/tasks/arc160_d 長さ $ 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 $ ずつ減らす。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $

答えを出力せよ。

### 制約 - $ 1\ \le\ K\ \le\ N\ \le\ 2000 $ - $ 1\ \le\ M\ \le\ 10^{18} $ ### Sample Explanation 1 条件を満たす数列は、以下の $ 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) $ となる。 ### Sample Explanation 2 条件を満たす数列が存在しない場合もあります。