Es gibt $N$ Städte und $M$ in beide Richtungen befahrbare Straßen. Die Städte sind von 1 bis $N$ nummeriert, die Straßen von 1 bis $M$. Die Straße $i$ verbindet die Städte $A_i$ und $B_i$ und hat die Länge $2^i$. Es ist garantiert, dass man über diese Straßen von jeder Stadt jede andere Stadt erreichen kann.

Snuke möchte eine Autofahrt unternehmen. Er möchte in Stadt 1 starten, jede Straße mindestens einmal befahren und nach Stadt 1 zurückkehren. Berechne die kleinstmögliche Länge seiner Route modulo $10^9 + 7$.

Eingabe

$$ \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$
• Über die Straßen kann man von jeder Stadt jede andere Stadt erreichen.
• Keine zwei Straßen verbinden dasselbe Paar von Städten.

Ausgabe

Gib die kleinstmögliche Länge von Snukes Route modulo $10^9 + 7$ aus.

Beispiele

Eingabe 1

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

Ausgabe 1

70

Eingabe 2

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

Ausgabe 2

2132

Hinweis

Zum Beispiel ist im ersten Beispiel $1 \to 2 \to 3 \to 4 \to 2 \to 3 \to 1$ eine optimale Route.