题目描述

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

输出格式

答えを出力せよ。

题目大意

题目描述

找到可以通过以下两种操作，使得长度为 $N$、元素之和为 $M$ 的数列 $A$ 全为 $0$ 的 $A$ 的个数，再取模 $998244353$。

1. 在 $A$ 中选一个元素，将其减去 $K$。
2. 在 $A$ 中选取长度为 $K$ 的子串，子串中每个元素减去 $1$。

输入格式

输入一行整数，分别代表 $N~M~K$。

输出格式

输出答案。

数据范围

• $1\le K\le N\le2000$
• $1\le M\le10^{18}$

3 2 2

5

100 998244353 100

0

2000 545782618661124208 533

908877889

提示

制約

• $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

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