配点 : $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$

出力

答えを出力せよ。

4 1 2

3

条件を満たす良い数列は以下の $3$ 個です。

• $(0,0,0,0)$
• $(0,1,0,1)$
• $(1,0,1,0)$

10 0 0

1

314 159 26535

248950743

$998244353$ で割ったあまりを答えてください。