• محدودیت زمان:‌ ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• منبع: آزمون مقدماتی اول دوره ۲۷ المپیاد کامپیوتر

---

کشور هیتایوتا از $ n $ شهر با شماره‌های $ 0 $ تا $ n - 1 $ تشکیل شده و جاده‌های آن به شکل یک $ n $ ضلعی منتظم است. پادشاه برای رفاه حال مردم $ m $ جاده دیگر ساخته است تا مردم بتوانند از این $ n + m $ جاده برای رفت و آمد خود استفاده کنند. (هر جاده دو شهر را با یک خط صاف به هم دیگر وصل می‌کند.)

پادشاه خیلی زود متوجه شد که نگه‌داری از این جاده‌ها کار بسیار هزینه‌بری است. برای همین او می‌خواهد تعدادی از جاده‌ها را خراب کند به صورتی که برای جاده‌های باقی‌مانده دو خاصیت زیر برقرار باشد:

• بین هر دو شهر دقیقا یک مسیر وجود داشته باشد.
• هیچ دو جاده‌ای یک‌دیگر را (جز در نقطه شروع و پایان) قطع نکنند.

پادشاه می‌خواد بداند با محدودیت‌های بالا به چند روش می‌تواند جاده‌ها را خراب کند. دو روش متفاوت است اگر و تنها اگر جاده‌ای وجود داشته باشد که در یکی از آن‌ها خراب شده باشد و در دیگری خراب نشده باشد. از آن‌جایی که این عدد می‌تواند خیلی بزرگ باشد پادشاه می‌خواد بداند باقی‌مانده تقسیم این عدد بر $10^9 + 7$ چند است.

ورودی

در خط اول ورودی دو عدد $ n $ و $ m $ آمده است که تعداد شهرها و تعداد جاده‌های اضافه شده را نشان می‌دهد.

در $ m $ خط بعدی در هر خط دو عدد $ u $ و $ v $ آمده است که نشان‌دهنده جاده‌ای بین شهر $ u $ و $ v $ است.

$$ 3 \le n \le 200$$

$$0 \le m \le \frac{n \times (n-3)}{2}$$

$$0 \le u_i, v_i \le n-1$$

بین هر دو شهر حداکثر یک جاده (از بین $ n + m $ جاده) وجود دارد و هیچ جاده‌ای یک شهر را به خودش وصل نمی‌کند.

خروجی

در تنها خط خروجی، عدد مورد نظر پادشاه را چاپ کنید.

زیرمسئله‌ها

زیرمسئله	نمره	محدودیت
۱	۱۳	$ n \le 7 $
۲	۲۱	یک سر جاده‌های اضافه شده، شهر با شماره $0$ است.
۳	۶۶	بدون محدودیت اضافی

مثال

ورودی نمونه

4 2
0 2
1 3

خروجی نمونه

12