+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- امیرمحمد یک گراف وزن‌دار **همبند $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 ```