Bessie und die Kühe benachbarter Höfe verbinden ihre Höfe durch Wege, um ein Bündnis gegen die Bauern zu bilden. Jeder der $N$ Höfe ($1 \le N \le 100,000$) sollte einen Weg zu genau einem anderen bauen, insgesamt $N$. Nach Monaten sind erst $M$ gebaut ($1 \le M < N$).

Streit darüber, welche Höfe bereits gebaut haben, bedroht das Bündnis. Zur Entspannung möchte Bessie die Bauweisen der bestehenden $M$ Wege zählen. Einen Weg zwischen 3 und 4 könnte Hof 3 oder Hof 4 gebaut haben. Zähle die Zuordnungen der Wege zu ihren Erbauerhöfen modulo 1,000,000,007. Sie unterscheiden sich, wenn mindestens ein Weg einen anderen Erbauer hat.

Eingabe

• Zeile 1: die ganzen Zahlen $N$ und $M$, getrennt durch ein Leerzeichen.
• Zeilen $2..1+M$: Zeile $i+1$ beschreibt Weg $i$ durch $u_{i}$ und $v_{i}$ mit Leerzeichen ($1 \le u_{i}, v_{i} \le N, u_{i} \ne v_{i}$), die verbundenen Höfe.

Ausgabe

• Zeile 1: die Anzahl Zuordnungen modulo 1,000,000,007. Erfüllt keine die Bedingungen, gib 0 aus.

Beispiele

Eingabe 1

5 4
1 2
3 2
4 5
4 5

Ausgabe 1

6

Hinweis

Zwischen demselben Paar Höfe können zwei Wege liegen.

Es gibt 6 Zuordnungen. $\{a,b,c,d\}$ bedeutet: Hof 1 baut Weg a, Hof 2 Weg b, Hof 3 Weg c und Hof 4 Weg d. Die Zuordnungen lauten: $\{2, 3, 4, 5\}$ $\{2, 3, 5, 4\}$ $\{1, 3, 4, 5\}$ $\{1, 3, 5, 4\}$ $\{1, 2, 4, 5\}$ $\{1, 2, 5, 4\}$

Aufgabenautor: Mark Gordon, 2011