Bessie i krowy sąsiednich farm postanowiły połączyć farmy ścieżkami, tworząc sojusz przeciw farmerom. Każdej z $N$ farm ($1 \le N \le 100,000$) polecono zbudować ścieżkę do dokładnie jednej innej, łącznie $N$. Po miesiącach zbudowano tylko $M$ ($1 \le M < N$).

Spory o to, które farmy już budowały, grożą rozpadem sojuszu. Bessie chce policzyć sposoby budowy istniejących $M$ ścieżek, łagodząc napięcia. Ścieżkę między 3 i 4 mogła zbudować farma 3 lub 4. Policz przypisania ścieżek farmom budowniczym modulo 1,000,000,007. Są różne, jeśli choć jedna ścieżka ma inną farmę budowniczą.

Wejście

• Wiersz 1: liczby całkowite $N$ i $M$ oddzielone spacją.
• Wiersze $2..1+M$: wiersz $i+1$ opisuje ścieżkę $i$ liczbami $u_{i}$ i $v_{i}$ oddzielonymi spacją ($1 \le u_{i}, v_{i} \le N, u_{i} \ne v_{i}$), połączone farmy.

Wyjście

• Wiersz 1: liczba przypisań modulo 1,000,000,007. Jeśli żadne nie spełnia warunków, wypisz 0.

Przykład

Wejście 1

5 4
1 2
3 2
4 5
4 5

Wyjście 1

6

Uwagi

Między tą samą parą farm mogą być dwie ścieżki.

Jest 6 przypisań. $\{a,b,c,d\}$ oznacza, że farma 1 buduje ścieżkę a, 2 ścieżkę b, 3 ścieżkę c, a 4 ścieżkę d. Przypisania to: $\{2, 3, 4, 5\}$ $\{2, 3, 5, 4\}$ $\{1, 3, 4, 5\}$ $\{1, 3, 5, 4\}$ $\{1, 2, 4, 5\}$ $\{1, 2, 5, 4\}$

Autor zadania: Mark Gordon, 2011