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

---

امیرمحمد یک گراف وزن‌دار همبند $n$ راسی با $m$ یال ($m > n$) دارد. در گراف وزن یال بین دو راس $x$ و $y$ را با $w_{x,y}$ نمایش می‌دهیم.
او شروع به بازی با این گراف می‌کند. در هر گام یک راس مثل $x$ که درجه‌اش دقیقا $2$ است (یعنی دو یال به این راس متصل است) و دو همسابه متمایز $y$ و $z$ دارد را انتخاب می‌کند و این راس و یالهای متصل به آن را حذف می‌کند. سپس یک یال بین دو راس $y$ و $z$ با وزن $max(w_{x,y}, w_{x, z})$ قرار می‌دهد. اما امیرمحمد خیلی کنترلی روی اعصابش ندارد و یک راس تصادفی $x$ انتخاب می‌کند و عملیات بالا را روی آن انجام می‌دهد (با احتمال یکسان بین انتخاب های ممکن).
می‌دانیم امیرمحمد $k$ بار این کار را انجام داده است. امید ریاضی مجموع وزن یال‌های درخت فراگیر کمینه (MST) گراف حاصل را پس از انجام $k$ مرحله بیابید.
فرض کنید پاسخ به صورت $\frac{P}{Q}$ باشد که $gcd(P, Q) = 1$. شما حاصل $P \times Q^{-1} \mod (10^9 + 7)$ را نمایش دهید.
تضمین می‌شود که در گراف داده شده در هر حالتی می‌توان $k$ بار چنین عملیاتی را انجام داد.

ورودی

سطر اول ورودی شامل سه عدد $n$ و $m$ و $k$ است. سپس در $m$ سطر بعدی، در هر سطر سه عدد $u_i$ و $v_i$ و $w_i$ آمده است که بیانگر یک یال بین $u_i$ و $v_i$ با وزن $w_i$ است.

• گراف در ابتدا یال چندگانه ندارد ولی ممکن است پس از انجام عملیات گفته‌شده یال چندگانه به‌وجود بیاید.
• $1 \le k < n < m \le 5 \times 10^{5}$
• $m <= \frac{n \times (n-1)}{2}$
• $1 \le u_i, v_i \le n$
• $1 \le w_i \le 10^9$
• $u_i \neq v_i$

خروجی

در تنها سطر خروجی خواسته مسئله را چاپ کنید.

زیر مسئله ها

زیرمسئله	نمره	محدودیت ها
۱	۱۳	$n \le 15$
۲	۲۰	$n \le 100$
۳	۲۰	$n \le 2000$
۴	۴۷	بدون محدودیت اضافی

مثال

ورودی نمونه ۱

4 5 1
1 2 1
2 3 2
3 1 3
1 4 4
2 4 4

خروجی نمونه ۱

4

ورودی نمونه ۲

6 7 1
1 2 1
2 3 2
3 4 3
4 5 4
5 6 5
6 1 6
1 4 7

خروجی نمونه ۲

12

ورودی نمونه ۳

4 5 1
1 2 1
2 3 1
3 1 1
1 4 2
2 4 2

خروجی نمونه ۳

500000006

ورودی نمونه ۴

6 7 2
1 2 1
2 3 2
3 4 3
4 5 4
5 6 5
6 1 6
1 4 7

خروجی نمونه ۴

9