分数: 800 点
问题陈述
求模数 998244353, 的 好的序列 长度 N 其元素是介于 0 和 M,包含在内,其总和最多为 K.
这里,长度-N 序列 X=(X_1,X_2,\ldots,X_N) 据说是好的当且仅当有一个图表 G 满足以下所有条件。
- G 是一个图表 N 顶点编号 1 to N 无自环。 (它可能有多边。)
- 对于每个 i\ (1\leq i \leq N),顶点的度数 i is 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.