+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- یک گراف ساده و **همبند** $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 ``` در گراف بالا هیچ عدد گذاری قابل قبولی وجود ندارد، چون به ازای هر عددگذاری حداقل دو راس مجاور وجود دارد که عدد نوشته شده روی آن‌ها یکسان خواهند داشت و این با خواسته سوال تناقض دارد.