Contest Duration: - (local time) (120 minutes) Back to Home
D - Mahjong /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

• 以下の操作のうちどちらかを選んで行うことを繰り返して、A の全ての要素を 0 にすることが出来る。
• 1 \le i \le N を満たす整数 i を選び、A_iK 減らす。
• 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


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

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

### 入力例 2

100 998244353 100


### 出力例 2

0


### 入力例 3

2000 545782618661124208 533


### 出力例 3

908877889


Score : 700 points

### 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.

### Constraints

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

### Input

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

N M K


### 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