Bessie và bò ở các trang trại gần đó quyết định nối trang trại bằng đường mòn để liên minh chống nông dân. Mỗi trang trại trong $N$ trang trại ($1 \le N \le 100,000$) được giao làm đường tới đúng một trang trại khác, tổng $N$ đường. Nhưng sau nhiều tháng chỉ có $M$ đường được làm ($1 \le M < N$).

Tranh cãi trang trại nào đã làm đường đe dọa chia rẽ liên minh. Bessie muốn đếm các cách làm $M$ đường hiện có để giảm căng thẳng. Đường giữa 3 và 4 có thể do trang trại 3 hoặc 4 làm. Đếm các cách gán đường cho trang trại đã làm, theo mô-đun 1,000,000,007. Hai cách khác nhau nếu ít nhất một đường có trang trại làm khác nhau.

Dữ liệu vào

• Dòng 1: hai số nguyên $N$ và $M$ cách nhau bởi dấu cách.
• Các dòng $2..1+M$: dòng $i+1$ mô tả đường $i$ bằng $u_{i}$ và $v_{i}$ cách nhau bởi dấu cách ($1 \le u_{i}, v_{i} \le N, u_{i} \ne v_{i}$), hai trang trại nối nhau.

Dữ liệu ra

• Dòng 1: số cách gán theo mô-đun 1,000,000,007. Nếu không cách nào thỏa mãn thì in 0.

Ví dụ

Dữ liệu vào 1

5 4
1 2
3 2
4 5
4 5

Dữ liệu ra 1

6

Ghi chú

Có thể có hai đường giữa cùng một cặp trang trại.

Có 6 cách. $\{a,b,c,d\}$ nghĩa là trang trại 1 làm đường a, 2 làm b, 3 làm c, 4 làm d. Các cách là: $\{2, 3, 4, 5\}$ $\{2, 3, 5, 4\}$ $\{1, 3, 4, 5\}$ $\{1, 3, 5, 4\}$ $\{1, 2, 4, 5\}$ $\{1, 2, 5, 4\}$

Tác giả: Mark Gordon, 2011