Có $N$ thành phố và $M$ con đường hai chiều. Các thành phố được đánh số từ $1$ đến $N$, còn các con đường được đánh số từ $1$ đến $M$. Con đường $i$ nối hai thành phố $A_i$ và $B_i$, có độ dài $2^i$. Đảm bảo rằng có thể đi từ bất kỳ thành phố nào đến bất kỳ thành phố nào bằng các con đường này.

Snuke muốn lái xe đi chơi. Anh ấy muốn xuất phát từ thành phố $1$, đi qua mỗi con đường ít nhất một lần rồi trở lại thành phố $1$. Hãy tính độ dài nhỏ nhất có thể của lộ trình, lấy modulo $10^9+7$.

Dữ liệu vào

$$ \begin{array}{cc} N & M\\ A_1 & B_1\\ \vdots & \\ A_M & B_M \end{array} $$

• $2\le N\le400000$
• $1\le M\le500000$
• $1\le A_i,B_i\le N$
• $A_i\ne B_i$
• Có thể đi từ bất kỳ thành phố nào đến bất kỳ thành phố nào bằng các con đường.
• Không có hai con đường nào nối cùng một cặp thành phố.

Dữ liệu ra

In ra độ dài nhỏ nhất có thể của lộ trình của Snuke, lấy modulo $10^9+7$.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

70

Dữ liệu vào 2

6 10
4 6
4 5
3 6
5 2
3 2
1 2
3 4
6 1
2 4
1 3

Dữ liệu ra 2

2132

Ghi chú

Chẳng hạn, trong ví dụ 1, một lộ trình tối ưu là $1\to2\to3\to4\to2\to3\to1$.