سرویس (Service)

امیرمحمد یک گراف وزن‌دار همبند $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 \le \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

توضیحات نمونه‌ها

  • در نمونه اول با احتمال $\frac{1}{2}$ راس $3$ انتخاب می‌شود و سپس پس از عملیات وزن زیر درخت کمینه فراگیر $5$ می‌شود. با احتمال $\frac{1}{2}$ راس $4$ انتخاب می‌شود و سپس پس از عملیات وزن زیر درخت کمینه فراگیر $3$ می‌شود. پس امید ریاضی $4$ است.
  • در نمونه دوم $4$ حالت انتخاب داریم و وزن‌های درخت کمینه $10, 11, 13, 14$ می‌شود. لذا امید ریاضی برابر با $12$ است.
  • در نمونه سوم در حالتی که عملیات روی راس $3$ اجرا شود جواب $3$ است. در حالتی که عملیات روی راس $4$ انجام شود، جواب $2$ است. بنابراین پاسخ نهایی $\frac{3}{2} + \frac{2}{2} = \frac{5}{2}$. $\frac{5}{2} \equiv 5 \times 500000004 \equiv 500000006 \ \mod (10^9 + 7)$