問題文
二王后君住在 Nico Nico 镇。 有 N 个路口,每个路口有 它的编号为 1 到 N 。另外,2 连接两个交叉路口 M 有一条书路,每条路都有 它的编号为 1 到 M 。路 i 当你经过十字路口时 A_i 到交叉路口 B_i 或交叉点 B_i 到交叉路口 A_i 至 您可以在 2^i 时间内前往那里。
二王后君要去兜风了。行驶路线是一个交叉路口 从 1 开始,M 至少预订所有道路 1 我不止一次经过路口。 我想创建一条返回 1 的路线。求沿着这样的路线行驶所需的最短时间。然而,答案可能非常大,所以 除以1,000,000,007 求余数。
入力
输入将以以下形式从标准输入给出。
N M A_1 B_1 A_2 B_2 : A_M B_M
- 1 行中,2 整数 N (2 ≦ N ≦ 400,000), M (1 ≦ M ≦ 500,000) 用空格分隔。这是Nico Nico镇的十字路口。 N 这条路是 M 表示这是一本书。 在
- 2 从线 M 行中,给出了道路信息。其中 给出了 i 行中,2 整数 A_i, B_i (1 ≦ A_i ≦ N, 1 ≦ B_i ≦ N, A_i ≠ B_i) 。这就是路 i 是一个交集 A_i 和交叉路口 B_i 已连接。在同一交叉路口连接各组的道路是 2 仅此而已。而且保证您可以从任意一个路口走多条路到达任意一个路口。
部分点
针对此问题设置了部分分数。 满足
- N ≦ 2,525 和 如果您对 M ≦ 2,525 的数据集 如果您正确回答 1 , 给出40 点。
- 如果所有测试用例都回答正确,除了上述之外 70 点。
出力
最短驱动时间 除以 1,000,000,007 后的余数 1 行输出。在输出末尾插入换行符。
入力例1
4 5 1 2 3 4 2 3 1 3 2 4
出力例1
70
在此输入示例中,Niconico Town 具有以下结构。
例如,交叉路口 遵循 1,2,3,4,2,3,1 顺序所需的时间 2^1 + 2^3 + 2^2 + 2^5 + 2^3 + 2^4 = 70 。
入力例2
6 10 4 6 4 5 3 6 5 2 3 2 1 2 3 4 6 1 2 4 1 3
出力例2
2132