Miasta partnerskie

Limit pamięci: 64MB

W Bajtocji jest n miast i między niektórymi parami miast są dwukierunkowe drogi. Drogi są w tak magiczny sposób ułożone, że między każdymi dwoma miastami istnieje dokładnie jeden sposób, by między nimi przejechać (być może odwiedzając inne miasta) i nie wjeżdżając do żadnego miasta dwa razy.

Król postanowił, wzorem europejskich miast, wprowadzić ideę miast partnerskich. Niestety, Bajtocja nie ma najlepszych kontaktów z sąsiadami, więc miastem partnerskim może być ew. inne miasto bajtockie. Dodatkowo, miasta partnerskie muszą być połączone bezpośrednią drogą. Dodatkowo, każde miasto może mieć co najwyżej jedno miasto partnerskie. I oczywiście jeśli A jest miastem partnerskim B, to B jest miastem partnerskim A.

Policz, na ile sposobów król może zarządzić, które pary miast mają być miastami partnerskimi. Miasto nie musi mieć miasta partnerskiego. Aby uprościć sobie życie, wypisz odpowiedź modulo 1 000 000 007.

Wejście, wyjście

W pierwszym wierszu wejścia są liczby n, m, 1 <= n, m <= 50 000, oznaczające liczbę miast i liczbę dróg w Bajtocji. Kolejne m wierszy opisuje drogi: dwie liczby od 1 do n, oznaczające miasta - końce i-tej drogi. Na wyjściu wypisz jedną liczbę: resztę z dzielenia liczby możliwych dekretów przez 1 000 000 007.

Przykład

Dla danych:

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

Prawidłową odpowiedzią jest:

17