Dwaj głupcy idą ulicą...

Pierwszy głupiec: Hej, wymyśliłem świetne zadanie. Masz graf skierowany acykliczny, czyli DAG... i chcesz przypisać każdej krawędzi wagę $0$ lub $1$, tak aby dla dowolnych dwóch wierzchołków waga ścieżki między nimi nie zależała od wyboru ścieżki...

Drugi głupiec: Hmm... ale co, jeśli między pewnymi dwoma wierzchołkami nie ma ścieżki?

Pierwszy głupiec: No tak, jeśli istnieje kilka ścieżek, wszystkie mają taką samą wagę. W każdym razie należy znaleźć liczbę takich przypisań wag.

Drugi głupiec: Tak, dobre zadanie...

Na szczęście spotkali wtedy swojego przyjaciela, który nie jest głupcem.

Nie-głupiec: Wy na pewno nie umiecie tego rozwiązać, innymi słowy, dziobiecie. Ale ja umiem rozwiązać nieco prostsze zadanie. Nie mogę wprawdzie wymagać, żeby odległość między wierzchołkami nie zależała od wyboru ścieżki, ale mogę wymagać, żeby odległość modulo $2$ nie zależała...

Pierwszy i drugi głupiec: orz

A teraz formalnie: dany jest graf skierowany z $N$ wierzchołkami i $M$ krawędziami. Wierzchołki są ponumerowane od $1$ do $N$, a dla każdej skierowanej krawędzi $(u,v)$ zachodzi $u<v$. Kolorowaniem krawędzi nazywamy przypisanie każdej krawędzi wartości $0$ lub $1$. Wartość krawędzi $(u,v)$ oznaczamy przez $w(u,v)$.

Ścieżką między wierzchołkami $u$ i $v$ jest dowolny ciąg wierzchołków $(a_1,\ldots,a_k)$ taki, że $a_1=u$ oraz $a_k=v$. Ponadto dla każdego $i$ od $1$ do $k-1$ istnieje krawędź $(a_i,a_{i+1})$. Waga ścieżki jest sumą wag wszystkich jej krawędzi, czyli $w(a_1,a_2)+\ldots+w(a_{k-1},a_k)$.

Kolorowanie $w$ jest dobre, jeśli dla każdej pary wierzchołków $(u,v)$ i każdej pary ścieżek między nimi wagi tych dwóch ścieżek dają taką samą resztę z dzielenia przez $2$.

Ponieważ liczba dobrych kolorowań może być duża, wypisz jej resztę z dzielenia przez $10^9+7$.

Wejście

W pierwszym wierszu znajdują się liczby naturalne $N$ i $M$.

W kolejnych $M$ wierszach znajdują się różne pary liczb $u$ i $v$ ($1\le u<v\le N$), oznaczające krawędzie grafu.

Wyjście

W jedynym wierszu należy wypisać resztę z dzielenia liczby dobrych kolorowań przez $10^9+7$.

Podzadania

We wszystkich podzadaniach zachodzi $1\le N\le 400$, $0\le M\le 400$.

Przykład

Wejście 1

4 4
1 2
2 3
3 4
1 4

Wyjście 1

8

Wejście 2

4 4
1 3
1 4
2 3
2 4

Wyjście 2

16

Uwagi

Ścieżki $1\to 2\to 3\to 4$ oraz $1\to 4$ muszą mieć takie same wagi modulo $2$. Jeśli krawędzi $(1,4)$ przypiszemy wagę $0$, parzysta liczba pozostałych krawędzi musi mieć wagę $1$, co daje $4$ kombinacje. Jeśli natomiast krawędzi $(1,4)$ przypiszemy wagę $1$, nieparzysta liczba pozostałych krawędzi musi mieć wagę $1$, co również daje $4$ kombinacje.