CF1925D.Good Trip

班上有 $n$ 个孩子，其中有 $m$ 对孩子是朋友。第 $i$ 对朋友的友谊值为 $f_i$。

老师需要组织 $k$ 次郊游，每次郊游她会随机、等概率、独立地选择一对孩子。如果选中的是一对朋友，则他们的友谊值会在之后的所有郊游中增加 $1$（老师可以多次选择同一对孩子）。不是朋友的孩子对的友谊值视为 $0$，且在之后的郊游中不会改变。

请你求出所有 $k$ 次郊游中，被选中对的友谊值之和的期望值（以被选中时的友谊值为准）。可以证明答案总能表示为最简分数 $\dfrac{p}{q}$，请计算 $p \cdot q^{-1} \bmod (10^9+7)$。

每个测试点包含多组测试数据。第一行包含测试用例数 $t$（$1 \le t \le 5 \cdot 10^4$）。每组测试数据描述如下。

每组测试数据的第一行包含三个整数 $n$、$m$ 和 $k$（$2 \le n \le 10^5$，$0 \le m \le \min(10^5, \frac{n(n-1)}{2})$，$1 \le k \le 2 \cdot 10^5$），分别表示孩子数、朋友对数和郊游次数。

接下来 $m$ 行，每行三个整数 $a_i$、$b_i$、$f_i$，表示第 $i$ 对朋友的编号和他们的友谊值（$a_i \neq b_i$，$1 \le a_i, b_i \le n$，$1 \le f_i \le 10^9$）。保证所有朋友对均不重复。

保证所有测试用例中 $n$ 的总和与 $m$ 的总和不超过 $10^5$，$k$ 的总和不超过 $2 \cdot 10^5$。

对于每组测试数据，输出一个整数，表示本题的答案。

对于第一个测试用例，没有朋友对，所以所有对的友谊值始终为 $0$，因此所有郊游的友谊值之和为 $0$。

对于第二个测试用例，只有一对 $(1, 2)$，初始友谊值为 $1$，每次被选中友谊值加 $1$，所以总和为 $1+2+3+\ldots+10=55$。

对于第三个测试用例，最终答案为 $\frac{7}{9}=777\,777\,784\bmod (10^9+7)$。

由 ChatGPT 4.1 翻译