题目描述

给定长度为$N$的序列，序列中的元素取值范围为$0$到$M$之间（包括$0$和$M$），且序列元素之和不超过$K$。求满足条件的长度为$N$的序列的数量（对$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$。

约束条件

• $4 \leq N \leq 3000$
• $0 \leq M \leq 3000$
• $0\leq K \leq NM$
• 输入的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$N$ $M$ $K$

输出

打印答案。

示例输入1

4 1 2

示例输出1

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$取模后输出结果。