You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小龙出发去旅行, 小龙年纪还比较小, 每新到一个地方, 会有一个紧张值, 但是这个紧张值会随着小龙旅行的城市变多, 而慢慢减小.

小龙一共要去$n$个点, 这$n$个点有$m$条双向边, 形成了一个联通图.

小龙已经确定了从 $1$ 号点出发, 在走的过程中, 可以重复经过同一个点, 但是已经旅游过的点小龙是不会再关注的. 他只会在到达一个新的点时, 记录下节点的编号. 最终$n$个点都到达过以后, 小龙开始计算他的总体紧张值.

总体紧张值是这么计算的:

首先得到一个序列:

• 小龙旅行过程中, 每当首次到达一个新的节点时, 就将这个节点的编号记录下来, 最终按顺序放置会得到一个长度为$n$的序列
• 假设序列中第一个编号为$a_1$, 第二个编号为$a_2$..., 第$n$个编号为$a_n$

其次, 小龙有一个特殊的紧张因子$s$, $s=$233333

第一次到达第一个城市, 紧张值为城市编号$a_1*s^n$

第一次到达第二个城市, 紧张值为城市编号$a_2*s^{n-1}$

依此类推, 第一次到达第$n$个城市, 紧张值为城市编号$a_n*s^{1}$

之后将这$n$次的紧张值求和, 即为总体紧张值.

现在想请你为小龙安排路线($1$号节点已经确认为出发点了, 即第一个到达的节点), 使得总体紧张值最小, 输出此总体紧张值. 由于此值可能很大, 你只需要输出对$10^9+7$取模的结果.

注意, 题目要求是总体紧张值最小, 而不是取模后的值最小.

输入格式

第一行两个整数$n$和$m$, 分别代表节点数和边数.

接下来$m$行, 描述无向边. 每行包含两个整数$u_i$和$v_i$, 代表一条连接$u_i$和$v_i$的边.

图中可能有多条边连接同样的一对节点(重边), 也可能有节点连向本身(自环).

保证图是联通的.

输出格式

输出一行一个整数, 代表最小的的总体紧张值, 输出时对$10^9+7$取模.

样例 #1

样例输入 #1

3 2
1 2
1 3

样例输出 #1

59688508

样例 #2

样例输入 #2

5 5
1 4
3 4
5 4
3 2
1 5

样例输出 #2

296945171

样例 #3

样例输入 #3

10 10
1 4
6 8
2 5
3 7
9 4
5 6
3 4
8 10
8 9
1 10

样例输出 #3

990633158

样例 #4/#5

见下发文件中ex_trip4/5.in/out

样例解释

对于样例$1$, 选择路径为$1 \rightarrow 2 \rightarrow 1 \rightarrow 3$可以获得最小总体紧张值. 得到的序列为$1, 2, 3$

对于样例$2$, 选择路径为$ 1 \rightarrow 4 \rightarrow 3 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 1 \rightarrow 5 $可以获得最小总体紧张值.

数据范围

对于$20\%$的数据, $1 \leq n \leq 5, 1 \leq m \leq 20$

对于$60\%$的数据, $1 \leq n \leq 15, 1 \leq m \leq 200$

对于$100\%$的数据, $1 \leq n, m \leq 10^5$, $1 \leq u_i, v_i \leq n$, 保证无向图为联通的

其他要求

每个测试点时限：$1$s 内存上限：$512$M