AT_arc156_e [ARC156E] Non-Adjacent Matching

给定一个长度为 $N$ 的整数序列，每个元素的取值范围为 $0$ 到 $M$，且所有元素的总和不超过 $K$。请你求出满足条件的**好数列**的个数，并将答案对 $998244353$ 取模。 这里，长度为 $N$ 的数列 $X=(X_1,X_2,\ldots,X_N)$ 被称为好数列，当且仅当存在一个满足以下所有条件的图 $G$： - $G$ 是一个有 $N$ 个顶点（编号为 $1$ 到 $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$

输出满足条件的好数列的个数，对 $998244353$ 取模后的结果。

### 限制 - $4 \leq N \leq 3000$ - $0 \leq M \leq 3000$ - $0 \leq K \leq NM$ - 输入的所有数均为整数 ### 样例解释 1 满足条件的好数列有以下 $3$ 个： - $(0,0,0,0)$ - $(0,1,0,1)$ - $(1,0,1,0)$ ### 样例解释 3 请将答案对 $998244353$ 取模后输出。 由 ChatGPT 4.1 翻译