← 返回题目列表

AtCoder · abc180_f

F. 无分支

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

分数: 600 点

问题陈述

查找图形的数量 N 标记的顶点和 M 未标记的边,不一定是简单的或连接的,满足以下条件,模 (10^9+7):

  • 不存在自环;
  • 每个顶点的度数最多为 2;
  • 连接组件的最大尺寸恰好是 L.

约束

  • 2 \leq N \leq 300
  • 1\leq M \leq N
  • 1 \leq L \leq N
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M L

输出

打印答案。


示例输入 1

3 2 3

示例输出 1

3

当顶点被标记时 1 通过 N,以下三张图满足条件:

  • 有边的图 1-2 和 2-3;
  • 有边的图 1-2 和 1-3;
  • 有边的图 1-3 和 2-3.

示例输入 2

4 3 2

示例输出 2

6

示例输入 3

300 290 140

示例输出 3

211917445