← 返回题目列表

AtCoder · arc156_e

E. 非相邻匹配

中文机器翻译题面 查看原题

分数: 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.