题目描述

長さが $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$ を意味する。

输入格式

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

$N$ $M$ $K$

输出格式

答えを出力せよ。

题目大意

定义一个长度为 $n$ 的序列 $X$ 是合法的，当且仅当存在一个无向图 $G$ 满足：

• $G$ 无自环（但可能有重边）。
• 对于所有 $1\le i\le n$，点 $i$ 的度数是 $X_i$。
• 对于所有的 $1\le i\le n$，不存在连接 $i$ 和 $i+1$ 的边。这里认为 $n+1$ 是 $1$。

求长度为 $n$，序列值域为 $[0,m]$，且序列的和小于等于 $k$ 的合法序列的个数，对 $998244353$ 取模。

$4\le n\le 3000,m\le 3000,k\le nm$

4 1 2

3

10 0 0

1

314 159 26535

248950743

提示

制約

• $4\ \leq\ N\ \leq\ 3000$
• $0\ \leq\ M\ \leq\ 3000$
• $0\leq\ K\ \leq\ NM$
• 入力される数値は全て整数

Sample Explanation 1

条件を満たす良い数列は以下の $3$ 個です。 - $(0,0,0,0)$ - $(0,1,0,1)$ - $(1,0,1,0)$

Sample Explanation 3

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