+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- یک گراف کامل $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`.