Problem Statement

Find the number, modulo 998244353, of sequences of $N non-negative integers A=(A_1,A_2,\dots,A_N) totaling M$ that satisfy the following condition.

• It is possible to make all elements of A equal 0 by repeatedly choosing one of the following operations and performing it.
• Choose an integer i such that $1 \le i \le N$ and decrease A_i by K.
• Choose an integer i such that $1 \le i \le N-K+1$ and decrease each of $A_i,A_{i+1},\dots,A_{i+K-1}$ by 1.

Input

The input is given from Standard Input in the following format:
N M K

Output

Print the answer.

Constraints

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

Sample Input 1

3 2 2

Sample Output 1

5

The following five sequences satisfy the requirements.

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

For instance, if A=(0,1,1), you can do the following to make all elements of A equal 0.

• Perform the second operation. Choose i = 2 to decrease each of A_2 and A_3 by 1, making A=(0,0,0).

Sample Input 2

100 998244353 100

Sample Output 2

0

There may be no sequence that satisfies the requirements.

Sample Input 3

2000 545782618661124208 533

Sample Output 3

908877889

见题面 Input 部分

见题面 Output 部分