/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
長さが N、各要素が 0 以上 M 以下、総和が K 以下の整数列のうち、良い数列 の個数を 998244353 で割ったあまりを求めてください。
ここで、長さ N の数列 X=(X_1,X_2,\ldots,X_N) は以下の条件を全て満たすグラフ G が存在するとき、かつ、そのときに限り良い数列です。
- G は 1 から N の番号がついた N 頂点からなる、自己ループを持たないグラフである。（多重辺はあってもよい。）
- 各 i\ (1\leq i \leq N) について、頂点 i の次数は X_i である。
- 各 i\ (1\leq i \leq N) について、頂点 i と頂点 i+1 を結ぶ辺は存在しない。ここで、頂点 N+1 は頂点 1 を意味する。
制約
- 4 \leq N \leq 3000
- 0 \leq M \leq 3000
- 0\leq K \leq NM
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M K
出力
答えを出力せよ。
入力例 1
4 1 2
出力例 1
3
条件を満たす良い数列は以下の 3 個です。
- (0,0,0,0)
- (0,1,0,1)
- (1,0,1,0)
入力例 2
10 0 0
出力例 2
1
入力例 3
314 159 26535
出力例 3
248950743
998244353 で割ったあまりを答えてください。
Score : 800 points
Problem Statement
Find the number, modulo 998244353, of good sequences of length N whose elements are integers between 0 and M, inclusive, and whose sum is at most K.
Here, a length-N sequence X=(X_1,X_2,\ldots,X_N) is said to be good if and only if there is a graph G that satisfies all of the following conditions.
- G is a graph with N vertices numbered 1 to N without self-loops. (It may have multi-edges.)
- For each i\ (1\leq i \leq N), the degree of vertex i is X_i.
- For each i\ (1\leq i \leq N), no edge connects vertex i and vertex i+1. Here, vertex N+1 means vertex 1.
Constraints
- 4 \leq N \leq 3000
- 0 \leq M \leq 3000
- 0\leq K \leq NM
- All numbers in the input are integers.
Input
The input is given from Standard Input in the following format:
N M K
Output
Print the answer.
Sample Input 1
4 1 2
Sample Output 1
3
The following three sequences are good.
- (0,0,0,0)
- (0,1,0,1)
- (1,0,1,0)
Sample Input 2
10 0 0
Sample Output 2
1
Sample Input 3
314 159 26535
Sample Output 3
248950743
Print the count modulo 998244353.