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

یک گراف کامل $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.