Edge Ordering

Cuber QQ 会给你一张 $n$ 个点 $m$ 条边的联通无向图 $G$，点从 $1$ 到 $n$ 编号，边从 $1$ 到 $m$ 编号。 Cuber QQ 给定的编号是精心设计的，编号为 $1$ 到 $n-1$ 的边恰好会构成图 $G$ 的一棵生成树 $T$。 Cuber QQ 要求你分别将 $[1,m]$ 中 $m$ 个数分配给每条边作为边权，需要保证任意两条边的边权都是不同的，即所有边的边权构成一个 $m$ 的全排列。 如果某一个分配方案中 $T$ 恰好是图 $G$ 的最小生成树，Cuber QQ 就认为这是一个优美的分配方案，而此时 $T$ 的边权和为该方案的价值。 现在 Cuber QQ 想知道所有优美的分配方案的价值总和。

[problemUrl]: https://atcoder.jp/contests/diverta2019/tasks/diverta2019_f $ 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 $

答えを出力せよ。

3 3
1 2
2 3
1 3

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

### 制約 - 入力は全て整数 - $ 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 $ の全域木となる ### Sample Explanation 1 \- 辺 $ 3 $ に重み $ 3 $ が割り当てられたときに限り、良い割り当てとなります。 - これらの良い割り当てにおける $ G $ の最小全域木に含まれる辺の重みの和は $ 3 $ であり、良い割り当ての個数は $ 2 $ つなので答えは $ 6 $ となります。 ### Sample Explanation 3 \- 総和を $ 10^{9}+7 $ で割ったあまりを出力してください。