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

یک گراف ساده و همبند $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

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