配点 : $1200$ 点

問題文

$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$ で割ったあまりを出力してください。

制約

• 入力は全て整数
• $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$

出力

答えを出力せよ。

3 3
1 2
2 3
1 3

6

• 辺 $3$ に重み $3$ が割り当てられたときに限り、良い割り当てとなります。
• これらの良い割り当てにおける $G$ の最小全域木に含まれる辺の重みの和は $3$ であり、良い割り当ての個数は $2$ つなので答えは $6$ となります。

4 4
1 2
3 2
3 4
1 3

50

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

657573092

• 総和を $10^{9}+7$ で割ったあまりを出力してください。