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

---

بعد از بیش از دو سال انتظار و جستجو برای هم تیمی، ابواسحاق متوجه شد کدکاپ ۵ انفرادی برگزار می‌شود! برای همین کلی ناراحت شد و رشته افکارش تبدیل به گراف شد! اکنون برای باز گرداندن آن به حالت عادی، دست به دامن شما شده است.

رشته افکار ابواسحاق یک گرافِ سادهٔ همبند \(n\) راسی و \(m\) یالی است. او تصمیم دارد برای بازگرداندن رشته افکارش در طی \(k\) مرحله، هر مرحله یک یال به آن اضافه کند به طوری که گراف حاصل، ساده باقی بماند و دارای حداقل یک دور به طول فرد باشد. (گراف ساده گرافی است که دارای یال چندگانه و طوقه نباشد)

امّا او که سلامت روانش بسیار برایش مهم است، قبل از این که دست به کار شود از شما می‌خواهد تا تعداد روش‌های مختلف انجام این عمل را به او بگویید. از آنجا که تعداد حالات، ممکن است بسیار زیاد باشد، باقی ماندهٔ تقسیم آن بر \(10^{9} + 7\) را به او بگویید (دو روش از انجام \(k\) مرحله را متمایز گوییم، اگر مرحله‌ای مثل \(i\) وجود داشته باشد که دو سر یال اضافه شده در روش اول برابر با دو سر یال اضافه شده در روش دوم نباشد).

دقت کنید که ترتیب اضافه کردن \(k\) یال اهمیت دارد.

ورودی

در خط اول ورودی سه عدد \(n\)، \(m\) و \(k\) آمده است.
در \(m\) خط بعدی دو عدد \(v\) و \(u\) آمده است، که نشان می‌دهد یک یال بین رئوس \(v\) و \(u\) وجود دارد.

\[3 \le n \le 1\ 000\] \[n-1 \le m < {n \choose 2}\] \[1 \le v, u \le n\] \[m + k \le {n \choose 2}\] \[1 \le k\]

تضمین می‌شود گراف ورودی، گرافی همبند و ساده است.

خروجی

در خروجی باید باقی‌مانده تعداد روش‌های خواسته شده بر \(10^{9} + 7\) را چاپ کنید.

مثال

ورودی نمونه ۱

4 3 2
1 2
2 3
3 4

خروجی نمونه ۱

6

توضیحات مثال

حالت های معتبر به شکل زیر هستند: \[{(1, 3), (1, 4)}\] \[{(1, 3), (2, 4)}\] \[{(1, 4), (2, 4)}\] \[{(1, 4), (1, 3)}\] \[{(2, 4), (1, 3)}\] \[{(2, 4), (1, 4)}\] هر سطر نشان دهندهٔ یک حالت از انجام \(k\) مرحله است. (\((i, j)\) نمایانگر کشیدن یال بین دو رأس \(i\) و \(j\) است و یال‌ها را در هر سطر از چپ به راست اضافه می‌کنیم)

ورودی نمونه ۲

3 2 1
1 2
1 3

خروجی نمونه ۲

1

تنها می‌توان یال \((2, 3)\) را اضافه کرد.