Eulerinen aliverkko on sellainen osajoukko verkon kaarista että jokaisen solmun aste on parillinen. Tulosta kuinka monta eulerista aliverkkoa syötteenä annetulla verkolla on modulo 10^9+7

Syöte

Ensimmäisellä rivillä on kaksi lukua, n ja m, verkon solmujen ja kaarien määrä. Seuraavalla m:llä rivillä on jokaisella kaksi lukua, a ja b, jotka tarkoittavat että verkossa on kaari solmujen a ja b välillä. Verkossa voi olla kaaria solmusta itseensä (tällöin molemmat päät nostavat solmun astelukua) ja verkossa voi olla useampia kaaria saman solmuparin välillä.

Tuloste

Tulosta yksi luku, euleristen aliverkkojen määrä modulo 10^9+7

Rajat

• 1 \le n \le 2 \cdot 10^5
• 0 \le m \le 2 \cdot 10^5

Esimerkki

Syöte:

4 4
1 2
1 3
1 4
2 3

Tuloste:

2

Syöte:

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

Tuloste:

4

Syöte:

2 3
1 1
1 2
1 2

Tuloste:

4

Syöte:

1 1
1 1

Tuloste:

2