AT_abc180_f [ABC180F] Unbranched

题目描述

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

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

输入格式

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

$N$ $M$ $L$

输出格式

输出答案。

样例 1

输入

3 2 3

输出

3

样例 2

输入

4 3 2

输出

6

样例 3

输入

300 290 140

输出

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 翻译