امیرمحمد یک گراف وزندار همبند $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$ است.
در تنها سطر خروجی خواسته مسئله را چاپ کنید.
| ورودی نمونه | خروجی نمونه |
|---|---|
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 |