Codeforces Round 921 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

dp

math

probabilities

*1900

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Good Trip

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThere are $$$n$$$ children in a class, $$$m$$$ pairs among them are friends. The $$$i$$$-th pair who are friends have a friendship value of $$$f_i$$$.

The teacher has to go for $$$k$$$ excursions, and for each of the excursions she chooses a pair of children randomly, equiprobably and independently. If a pair of children who are friends is chosen, their friendship value increases by $$$1$$$ for all subsequent excursions (the teacher can choose a pair of children more than once). The friendship value of a pair who are not friends is considered $$$0$$$, and it does not change for subsequent excursions.

Find the expected value of the sum of friendship values of all $$$k$$$ pairs chosen for the excursions (at the time of being chosen). It can be shown that this answer can always be expressed as a fraction $$$\dfrac{p}{q}$$$ where $$$p$$$ and $$$q$$$ are coprime integers. Calculate $$$p\cdot q^{-1} \bmod (10^9+7)$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$). Description of the test cases follows.

The first line of each test case contains $$$3$$$ integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$2 \le n \le 10^5$$$, $$$0 \le m \le \min \Big(10^5$$$, $$$ \frac{n(n-1)}{2} \Big)$$$, $$$1 \le k \le 2 \cdot 10^5$$$) — the number of children, pairs of friends and excursions respectively.

The next $$$m$$$ lines contain three integers each — $$$a_i$$$, $$$b_i$$$, $$$f_i$$$ — the indices of the pair of children who are friends and their friendship value. ($$$a_i \neq b_i$$$, $$$1 \le a_i,b_i \le n$$$, $$$1 \le f_i \le 10^9$$$). It is guaranteed that all pairs of friends are distinct.

It is guaranteed that the sum of $$$n$$$ and sum $$$m$$$ over all test cases does not exceed $$$10^5$$$ and the sum of $$$k$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print one integer — the answer to the problem.

Example

Input

4100 0 242 1 101 2 13 1 22 1 15 2 41 2 253 2 24

Output

0 55 777777784 40000020

Note

For the first test case, there are no pairs of friends, so the friendship value of all pairs is $$$0$$$ and stays $$$0$$$ for subsequent rounds, hence the friendship value for all excursions is $$$0$$$.

For the second test case, there is only one pair possible $$$(1, 2)$$$ and its friendship value is initially $$$1$$$, so each turn they are picked and their friendship value increases by $$$1$$$. Therefore, the total sum is $$$1+2+3+\ldots+10 = 55$$$.

For the third test case, the final answer is $$$\frac{7}{9} = 777\,777\,784\bmod (10^9+7)$$$.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/17/2024 21:56:42 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|