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

---

یک گراف ساده و همبند \(n\) راسی و \(m\) یالی داریم. می‌خواهیم روی هر راس این گراف یک عدد از مجموعه \(\{ 1, 2, 3, \dots, k\}\) بنویسیم.

اگر عدد نوشته شده روی راس \(v\) را با \(a_v\) و طول کوتاه ترین مسیر بین دو راس \(u\) و \(v\) را با \(dist(u, v)\) نشان دهیم.

می‌خواهیم این عدد گذاری به گونه‌ای انجام شود که برای هر دو راس از این گراف مثل \(u\) و \(v\) داشته باشیم.

\[dist(u, v) = |a_u - a_v|\]

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

ورودی

خط اول ورودی به ترتیب سه عدد \(n\) و \(m\) و \(k\) با فاصله از هم آمده‌اند.

\[1 \le n \le 100\ 000\] \[n - 1 \leq m \leq min(\frac{n(n - 1)}{2},100 \, 000)\] \[1 \le k \le 10^9\]

در \(m\) خط بعدی و در هر خط دو عدد \(v\) و \(u\) با فاصله از هم آمده‌اند که نشان‌دهنده‌ی یالی بین دو رأس \(v\) و \(u\) هستند. \[1 \le v, u \le n\]

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

خروجی

مثال

ورودی نمونه ۱

2 1 3
1 2

خروجی نمونه ۱

4

اگر عدد نوشته شده روی راس شماره \(v\) را با \(c(v)\) نشان دهیم؛ ۴ روش زیر برای این عدد گذاری وجود دارد.

• \(c(1) = 1, c(2) = 2\)
• \(c(1) = 2, c(2) = 1\)
• \(c(1) = 3, c(2) = 2\)
• \(c(1) = 2, c(2) = 3\)

ورودی نمونه ۲

3 3 2
1 2
2 3
3 1

خروجی نمونه ۲

0

در گراف بالا هیچ عدد گذاری قابل قبولی وجود ندارد، چون به ازای هر عددگذاری حداقل دو راس مجاور وجود دارد که عدد نوشته شده روی آن‌ها یکسان خواهند داشت و این با خواسته سوال تناقض دارد.