有 $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$。