AT_abc180_f [ABC180F] Unbranched

题目描述

给定一个有 $N$ 个顶点、$M$ 条边的无向图，顶点有标签，边没有标签。该图不一定是简单图，也不一定是连通图。请计算满足以下条件的图的数量，并将结果对 $10^9+7$ 取模：

• 不包含自环。
• 所有顶点的度数都不超过 $2$。
• 将每个连通分量的大小按升序排列后，最大值恰好为 $L$。

输入格式

输入从标准输入中读取，格式如下：

$N$ $M$ $L$

输出格式

输出答案。

输入输出样例 #1

输入 #1

3 2 3

输出 #1

3

输入输出样例 #2

输入 #2

4 3 2

输出 #2

6

输入输出样例 #3

输入 #3

300 290 140

输出 #3

211917445

说明/提示

限制条件

• $2 \leq N \leq 300$
• $1 \leq M \leq N$
• $1 \leq L \leq N$
• 输入均为整数。

样例解释 1

当顶点编号为 $1$ 到 $N$ 时，满足条件的图有以下 $3$ 种情况：

• $1$ 与 $2$ 相连，$2$ 与 $3$ 相连。
• $1$ 与 $2$ 相连，$1$ 与 $3$ 相连。
• $1$ 与 $3$ 相连，$2$ 与 $3$ 相连。

由 ChatGPT 4.1 翻译