题目描述

给定一个简单连通无向图 $G$，它由 $N$ 个顶点和 $M$ 条边组成。顶点从 $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$ 的最小生成树时。

有 $M!$ 种方式在 $1$ 到 $M$ 之间为边分配不同的整数权重。找出所有好的分配中，最小生成树中所有边的总权重，并将这些总权重之和对 $10^{9}+7$ 取模后的结果。

约束条件

• 输入中的所有值均为整数。
• $2 \\leq N \\leq 20$
• $N-1 \\leq M \\leq N(N-1)/2$
• $1 \\leq a_i, b_i \\leq N$
• $G$ 中没有自环和重边。
• 由顶点 $1, 2, \\ldots, N$ 和边 $1, 2, \\ldots, N-1$ 构成的子图是 $G$ 的生成树。

输入

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

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

输出

打印答案。

示例输入 1

3 3
1 2
2 3
1 3

示例输出 1

6

只有当边 $3$ 的权重为 $3$ 时，分配才是好的。在这些好的分配中，最小生成树中所有边的总权重为 $3$，所以答案是 $6$。

示例输入 2

4 4
1 2
3 2
3 4
1 3

示例输出 2

50

示例输入 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

对 $10^{9}+7$ 取模得到的总权重之和。