题目描述

给定一个包含 $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$

输出格式

输出答案。

输入输出样例 #1

输入 #1

3 3
1 2
2 3
1 3

输出 #1

6

输入输出样例 #2

输入 #2

4 4
1 2
3 2
3 4
1 3

输出 #2

50

输入输出样例 #3

输入 #3

15 28
10 7
5 9
2 13
2 14
6 1
5 12
2 10
3 9
10 15
11 12
12 6
2 12
12 8
4 10
15 3
13 14
1 15
15 12
4 14
1 7
5 11
7 13
9 10
2 7
1 9
5 6
12 14
5 2

输出 #3

657573092

说明/提示

限制条件

• 所有输入均为整数。
• $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$ 取模后输出。