Istnieje $N$ miast i $M$ dróg dwukierunkowych. Miasta są ponumerowane od $1$ do $N$, a drogi od $1$ do $M$. Droga $i$ łączy miasta $A_i$ i $B_i$, a jej długość wynosi $2^i$. Zagwarantowano, że tymi drogami można dotrzeć z dowolnego miasta do dowolnego innego miasta.

Snuke chce wybrać się na przejażdżkę. Chce wyruszyć z miasta $1$, przejechać każdą drogą co najmniej raz i wrócić do miasta $1$. Oblicz najmniejszą możliwą długość jego trasy modulo $10^9+7$.

Wejście

$$ \begin{gathered} N\quad M\\ A_1\quad B_1\\ \vdots\\ A_M\quad 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$
• Korzystając z dróg, można dotrzeć z dowolnego miasta do dowolnego innego miasta.
• Żadne dwie drogi nie łączą tej samej pary miast.

Wyjście

Wypisz najmniejszą możliwą długość trasy Snuke'a modulo $10^9+7$.

Przykład

Wejście 1

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

Wyjście 1

70

Wejście 2

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

Wyjście 2

2132

Uwagi

Na przykład w pierwszym przykładzie jedną z optymalnych tras jest $1 \to 2 \to 3 \to 4 \to 2 \to 3 \to 1$.