• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

یک گراف کامل \(n\) راسی \(G\) به شما داده می‌شود که \(m\) تا از راس‌های آن، به صورت دلخواه با اعداد \(1\) تا \(m\) شماره‌گذاری شده‌اند و \(n - m\) راس دیگر گراف، با یکدیگر یکسان هستند و همگی آن‌ها شماره \(0\) دارند.

هم‌چنین \(e\) یال از گراف \(G\) حذف شده‌ است به طوری که شماره راس دو سر هر کدام از این یال‌ها بین \(1\) و \(m\) می‌باشد.

شما باید تعداد مسیر‌های به طول \(n - 1\) در گراف \(n\) راسی \(G\) (در واقع تعداد مسیرهای هامیلتونی) را خروجی دهید.

دو مسیر در گراف متفاوت درنظر گرفته می‌شوند اگر دنباله‌های راسی آن‌ها متفاوت باشند، برای مثال دو مسیر \(1\ 0\ 2\ 3\) و \(1\ 0\ 2\ 3\) با یکدیگر یکسان و دو مسیر \(0\ 2\ 1\ 0\) و \(0\ 1\ 2\ 0\) با یکدیگر متفاوت هستند.

از آنجایی که جواب ممکن است بزرگ باشد، جواب را به باقیمانده \(10^9 + 7\) چاپ کنید.

ورودی

در خط اول ورودی به ترتیب سه عدد \(n\) و \(m\) و \(e\) داده می‌شود.

در \(e\) خط بعدی ورودی, در هر خط دو عدد \(u\) و \(v\) به شما داده می‌شود که بیانگر این است که یال بین دو راسی که با \(u\) و \(v\) شماره‌گذاری شده‌اند حذف شده‌است.

تضمین می‌شود که هر یال حداکثر یک‌بار حذف می‌شود. \[ 1 \le n \le 10^{18} \] \[ 1 \le m \le 16 \] \[ m \le n \] \[ 0 \le e \le \frac{m(m - 1)}{2} \] \[ 1 \le u, v \le m \]

خروجی

در تنها خط خروجی، یک عدد خروجی دهید که بیانگر تعداد مسیرهای به طول \(n - 1\) در گراف \(G\) به باقیمانده \(10^9 + 7\) می‌باشد.

مثال

ورودی نمونه ۱

4 3 2
1 2
1 3

خروجی نمونه ۱

4

مسیرهای هامیلتونی متفاوت عبارت‌اند از 1 0 3 2 و 1 0 2 3 و 2 3 0 1 و 3 2 0 1.

ورودی نمونه ۲

3 3 1
2 3

خروجی نمونه ۲

2

مسیرهای هامیلتونی متفاوت عبارت‌اند از 2 1 3 و 3 1 2.