Syrjälän asukkaat pelaavat usein jalkapalloa keskenään. Peliä varten asukkaat jaetaan kahteen joukkueeseen. Kuitenkin aina joskus kaksi asukasta riitaantuvat keskenään, eivätkä halua enää ikinä pelata samassa joukkueessa. Kun annetaan lista tapahtumista muotoa "asukas $a$ riitaantui asukkaan $b$ kanssa", selvitä jokaisen tapahtuman jälkeen kuinka monella tavalla asukkaat voidaan jakaa kahteen joukkueeseen. Ilmoita vastaus modulo $10^9+7$.

Syöte

Syötteen ensimmäisellä rivillä on kaksi lukua, $n$ ja $m$, asukkaiden määrä ja tapahtumien määrä. Seuraavilla $m$:llä rivillä on jokaisella kaksi lukua $a_i$ ja $b_i$, jotka tarkoittavat että asukas $a_i$ riitaantui asukkaan $b_i$ kanssa.

Tuloste

Tulosta $m$ lukua, kuinka monella tavalla asukkaat voidaan jakaa kahteen joukkueeseen jokaisen tapahtuman jälkeen modulo $10^9+7$.

Rajat

• $2 \le n \le 10^5$
• $1 \le m \le 2 \cdot 10^5$
• $1 \le a_i, b_i \le n, a_i \neq b_i$

Esimerkki

Syöte:

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

Tuloste:

8
4
2
1
1
0