Bessie và những người bạn bò ở các trang trại gần đó cuối cùng đã quyết định nối các trang trại với nhau bằng những con đường mòn nhằm lập liên minh chống lại các nông dân. Ban đầu, đàn bò ở mỗi trong số \(N\) trang trại (\(1 \le N \le 100\,000\)) được yêu cầu xây một đường mòn đến đúng một trang trại khác, tạo thành tổng cộng \(N\) đường mòn. Tuy nhiên, sau nhiều tháng thực hiện dự án, mới chỉ có \(M\) (\(1 \le M < N\)) đường mòn thực sự được xây.

Những cuộc tranh cãi giữa các trang trại về việc trang trại nào đã xây một đường mòn giờ đây đe dọa chia rẽ liên minh bò. Để xoa dịu căng thẳng, Bessie muốn tính xem \(M\) đường mòn hiện có có thể đã được xây theo bao nhiêu cách. Ví dụ, nếu có một đường mòn nối trang trại 3 và 4, một khả năng là trang trại 3 đã xây đường mòn đó, còn khả năng kia là trang trại 4 đã xây nó. Hãy giúp Bessie tính số cách khác nhau để gán mỗi đường mòn cho trang trại đã xây nó, lấy modulo \(1\,000\,000\,007\). Hai cách gán được coi là khác nhau nếu có ít nhất một đường mòn được xây bởi hai trang trại khác nhau trong hai cách gán.

Dữ liệu vào

• Dòng 1 chứa hai số nguyên \(N\) và \(M\), cách nhau bởi dấu cách.
• Các dòng từ 2 đến \(1+M\): dòng \(i+1\) mô tả đường mòn thứ \(i\). Mỗi dòng chứa hai số nguyên \(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\)), mô tả cặp trang trại được đường mòn nối với nhau.

Dữ liệu ra

In một dòng duy nhất chứa số cách gán các đường mòn cho các trang trại, lấy modulo \(1\,000\,000\,007\). Nếu không có cách gán nào thỏa mãn các điều kiện trên, in ra 0.

Ví dụ

5 4
1 2
3 2
4 5
4 5

6

Nguồn

USACO 2012 January Contest, Gold - Bovine Alliance: https://usaco.org/index.php?page=viewproblem2&cpid=111

Tác giả: Mark Gordon, 2011.