题目描述

给定一个长度为 $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$ 取模后的结果。

样例 1

输入

4 1 2

输出

3

样例 2

输入

10 0 0

输出

1

样例 3

输入

314 159 26535

输出

248950743

说明/提示

限制

• $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 翻译