311040: CF1925D. Good Trip

D. Good Triptime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

There 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.

ExampleInput

4
100 0 24
2 1 10
1 2 1
3 1 2
2 1 1
5 2 4
1 2 25
3 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)$.

题目大意：
一个班级里有n个孩子，其中有m对是朋友，每对朋友的友谊值为f_i。老师要进行k次远足，每次随机等概率独立地选择一对孩子。如果选中的是一对朋友，他们的友谊值在后续的远足中都会增加1（老师可能多次选择同一对孩子）。如果选中的不是朋友，则他们的友谊值被认为是0，并且在后续远足中不会改变。求出所有k次远足中选中的孩子对的友谊值之和的期望值。答案可以表示为分数p/q，其中p和q是互质的整数。计算p * q^(-1) mod (10^9+7)。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤5 * 10^4），表示测试用例的数量。
- 每个测试用例的第一行包含三个整数n、m和k（2≤n≤10^5，0≤m≤min(10^5, n(n-1)/2)，1≤k≤2 * 10^5），分别表示孩子的数量、朋友对的数量和远足的次数。
- 接下来的m行，每行包含三个整数a_i、b_i和f_i（a_i≠b_i，1≤a_i,b_i≤n，1≤f_i≤10^9），表示一对朋友的孩子的索引和他们的友谊值。保证所有的朋友对都是不同的。
- 保证所有测试用例的n和m的总和不超过10^5，k的总和不超过2 * 10^5。

输出：
- 对于每个测试用例，输出一个整数，表示问题的答案。题目大意： 一个班级里有n个孩子，其中有m对是朋友，每对朋友的友谊值为f_i。老师要进行k次远足，每次随机等概率独立地选择一对孩子。如果选中的是一对朋友，他们的友谊值在后续的远足中都会增加1（老师可能多次选择同一对孩子）。如果选中的不是朋友，则他们的友谊值被认为是0，并且在后续远足中不会改变。求出所有k次远足中选中的孩子对的友谊值之和的期望值。答案可以表示为分数p/q，其中p和q是互质的整数。计算p * q^(-1) mod (10^9+7)。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤5 * 10^4），表示测试用例的数量。 - 每个测试用例的第一行包含三个整数n、m和k（2≤n≤10^5，0≤m≤min(10^5, n(n-1)/2)，1≤k≤2 * 10^5），分别表示孩子的数量、朋友对的数量和远足的次数。 - 接下来的m行，每行包含三个整数a_i、b_i和f_i（a_i≠b_i，1≤a_i,b_i≤n，1≤f_i≤10^9），表示一对朋友的孩子的索引和他们的友谊值。保证所有的朋友对都是不同的。 - 保证所有测试用例的n和m的总和不超过10^5，k的总和不超过2 * 10^5。 输出： - 对于每个测试用例，输出一个整数，表示问题的答案。