CSES - Euler^1
  • Time limit: 2.00 s
  • Memory limit: 512 MB

Eulerinen aliverkko on sellainen osajoukko verkon kaarista että jokaisen solmun aste on parillinen. Tehtävänäsi on laskea verkon euleristen aliverkkojen kokojen summa modulo 10^9+7. Eulerisen aliverkon koko on siinä olevien kaarien määrä.

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 kokojen summa 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:

3

Syöte:

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

Tuloste:

12

Syöte:

2 3
1 1
1 2
1 2

Tuloste:

6

Syöte:

1 1
1 1

Tuloste:

1