有 $N$ 座城市同 $M$ 條雙向道路。城市編號由 $1$ 到 $N$，道路編號由 $1$ 到 $M$。第 $i$ 條道路連接城市 $A_i$ 同 $B_i$，長度係 $2^i$。保證可以沿住呢啲道路由任何一座城市去到任何另一座城市。

Snuke 想去揸車。佢想由城市 $1$ 出發，每條道路至少經過一次，再返到城市 $1$。計算佢路線可能嘅最短長度，答案對 $10^9+7$ 取模。

輸入格式

$$ \begin{gathered} N\ M\\ A_1\ B_1\\ \vdots\\ A_M\ B_M \end{gathered} $$

• $2 \le N \le 400000$
• $1 \le M \le 500000$
• $1 \le A_i,B_i \le N$
• $A_i \ne B_i$
• 可以沿住道路由任何一座城市去到任何另一座城市。
• 冇兩條道路連接同一對城市。

輸出格式

輸出 Snuke 路線可能嘅最短長度，答案對 $10^9+7$ 取模。

樣例

輸入格式 1

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

輸出格式 1

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

說明

例如，喺樣例 1 中，一條最優路線係 $1 \to 2 \to 3 \to 4 \to 2 \to 3 \to 1$。