Bessie e le mucche vicine collegano le fattorie con sentieri per allearsi contro i contadini. Ognuna delle $N$ fattorie ($1 \le N \le 100,000$) doveva costruire un sentiero verso esattamente un’altra, per un totale di $N$. Dopo mesi, solo $M$ sono costruiti ($1 \le M < N$).

Le discussioni su chi ha già costruito minacciano l’alleanza. Bessie vuole contare i modi di costruire gli $M$ sentieri esistenti per allentare la tensione. Uno tra 3 e 4 può essere stato costruito dalla fattoria 3 o 4. Conta le assegnazioni dei sentieri alle fattorie costruttrici modulo 1,000,000,007. Sono diverse se almeno un sentiero ha costruttrice diversa.

Input

• Riga 1: gli interi $N$ e $M$ separati da uno spazio.
• Righe $2..1+M$: la riga $i+1$ descrive il sentiero $i$ con $u_{i}$ e $v_{i}$ separati da uno spazio ($1 \le u_{i}, v_{i} \le N, u_{i} \ne v_{i}$), le fattorie collegate.

Output

• Riga 1: il numero di assegnazioni modulo 1,000,000,007. Se nessuna soddisfa le condizioni, stampa 0.

Esempi

Input 1

5 4
1 2
3 2
4 5
4 5

Output 1

6

Spiegazione

Possono esserci due sentieri tra la stessa coppia di fattorie.

Ci sono 6 assegnazioni. $\{a,b,c,d\}$ significa che la fattoria 1 costruisce il sentiero a, la 2 il b, la 3 il c e la 4 il d. Le assegnazioni sono: $\{2, 3, 4, 5\}$ $\{2, 3, 5, 4\}$ $\{1, 3, 4, 5\}$ $\{1, 3, 5, 4\}$ $\{1, 2, 4, 5\}$ $\{1, 2, 5, 4\}$

Autore: Mark Gordon, 2011