AT_diverta2019_f.Edge Ordering

给定一个包含 $N$ 个顶点和 $M$ 条边的简单连通无向图 $G$。顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。

第 $i$ 条边是连接顶点 $a_i$ 和 $b_i$ 的无向边。保证由顶点 $1,2,\ldots,N$ 和边 $1,2,\ldots,N-1$ 构成的子图是 $G$ 的一棵生成树。

如果对边赋予权值，使得由顶点 $1,2,\ldots,N$ 和边 $1,2,\ldots,N-1$ 构成的树成为 $G$ 的最小生成树，则称这样的权值分配为“良好分配”。

每条边都要被分配一个 $1$ 到 $M$ 的互不相同的整数权值。这样的分配方式共有 $M!$ 种。在所有良好分配中，计算最小生成树中包含的边的权值之和，并将这些和的总和对 $10^9+7$ 取模后输出。

输入以如下格式从标准输入读入：

$N$ $M$
$a_1$ $b_1$
$\vdots$
$a_M$ $b_M$

输出答案。

限制条件

• 所有输入均为整数。
• $2 \leq N \leq 20$
• $N-1 \leq M \leq \frac{N(N-1)}{2}$
• $1 \leq a_i, b_i \leq N$
• 图 $G$ 中不存在自环或重边。
• 由顶点 $1,2,\ldots,N$ 和边 $1,2,\ldots,N-1$ 构成的子图是 $G$ 的一棵生成树。

样例解释 1

• 只有当第 $3$ 条边被分配权值 $3$ 时，才是良好分配。
• 在这些良好分配中，最小生成树中包含的边的权值之和为 $3$，良好分配的数量为 $2$，因此答案为 $6$。

样例解释 3

• 请将总和对 $10^9+7$ 取模后输出。

由 ChatGPT 4.1 翻译