有 $N$ 个城市和 $M$ 条双向道路。城市编号为 $1$ 到 $N$，道路编号为 $1$ 到 $M$。第 $i$ 条道路连接城市 $A_i$ 和 $B_i$，其长度为 $2^i$。保证可以通过这些道路从任意城市到达任意其他城市。

Snuke 想要开车。他希望从城市 $1$ 出发，经过每一条道路至少一次，并最终回到城市 $1$。计算他路线的最短总长度，对 $10^9 + 7$ 取模。

输入格式

第一行包含两个整数 $N$ 和 $M$。 接下来的 $M$ 行，每行包含两个整数 $A_i$ 和 $B_i$。

• $2 \le N \le 400000$
• $1 \le M \le 500000$
• $1 \le A_i, B_i \le N$
• $A_i \neq B_i$
• 保证可以通过道路从任意城市到达任意其他城市。
• 没有两条道路连接同一对城市。

输出格式

输出 Snuke 路线的最短总长度，对 $10^9 + 7$ 取模。

样例

输入格式 1

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

输出格式 1

70

说明

例如，在样例 1 中，一条最优路线是 $1 \to 2 \to 3 \to 4 \to 2 \to 3 \to 1$。

输入格式 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