قررت Bessie وأبقار المزارع القريبة وصل مزارعها بممرات للتحالف ضد المزارعين. كلفت كل مزرعة من الـ $N$ ($1 \le N \le 100,000$) ببناء ممر إلى مزرعة أخرى واحدة بالضبط، بمجموع $N$ ممر. لكن بعد أشهر لم يبن إلا $M$ ($1 \le M < N$).

تهدد الخلافات حول المزارع التي بنت بالفعل بانقسام التحالف. تريد Bessie عد طرق بناء الممرات الـ $M$ الموجودة لتهدئة التوتر. الممر بين 3 و4 قد تبنيه المزرعة 3 أو 4. احسب إسنادات الممرات إلى المزارع البانية بترديد 1,000,000,007. يختلف إسنادان إذا اختلفت المزرعة البانية لممر واحد على الأقل.

الإدخال

• السطر 1: العددان الصحيحان $N$ و$M$ مفصولان بفراغ.
• الأسطر $2..1+M$: يصف السطر $i+1$ الممر $i$ بالعددين $u_{i}$ و$v_{i}$ مفصولين بفراغ ($1 \le u_{i}, v_{i} \le N, u_{i} \ne v_{i}$)، وهما المزرعتان الموصولتان.

الإخراج

• السطر 1: عدد الإسنادات بترديد 1,000,000,007. إذا لم يحقق أي إسناد الشروط فاطبع 0.

أمثلة

الإدخال 1

5 4
1 2
3 2
4 5
4 5

الإخراج 1

6

ملاحظة

قد يوجد ممران بين الزوج نفسه من المزارع.

توجد 6 إسنادات. تعني $\{a,b,c,d\}$ أن المزرعة 1 تبني الممر a و2 تبني b و3 تبني c و4 تبني d. الإسنادات هي: $\{2, 3, 4, 5\}$ $\{2, 3, 5, 4\}$ $\{1, 3, 4, 5\}$ $\{1, 3, 5, 4\}$ $\{1, 2, 4, 5\}$ $\{1, 2, 5, 4\}$

مؤلف المسألة: Mark Gordon، 2011