D - Mahjong Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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 K \le N \le 2000
  • 1 \le M \le 10^{18}

入力

入力は以下の形式で標準入力から与えられる。

N M K

出力

答えを出力せよ。

入力例 1

3 2 2

出力例 1

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

入力例 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

Output

Print the answer.

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