← 返回题目列表

Codeforces · 1925/D

D. 旅途愉快

中文机器翻译题面 查看原题

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

老师必须进行 $$$k$$$ 短途旅行,并且对于每次短途旅行,她都会随机、等概率且独立地选择一对孩子。如果选择一对是朋友的孩子,他们的友谊值在所有后续旅行中都会增加$$$1$$$(老师可以多次选择一对孩子)。一对非朋友的友谊值被视为 $$$0$$$,并且不会因后续旅行而改变。

找出为短途旅行选择的所有 $$$k$$$ 对的友谊值总和的预期值(在选择时)。可以证明,这个答案总是可以表示为分数 $$$\dfrac{p}{q}$$$,其中 $$$p$$$ 和 $$$q$$$ 是互质整数。计算$$$p\cdot q^{-1} \bmod (10^9+7)$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含 $$$3$$$ 整数 $$$n$$$、$$$m$$$ 和 $$$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$$$) — 分别为儿童、朋友对和短途旅行的数量。

接下来的 $$$m$$$ 行每行包含三个整数 - $$$a_i$$$、$$$b_i$$$、$$$f_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$$$。

输出

对于每个测试用例,打印一个整数 - 问题的答案。

示例

输入 #1

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

输出 #1

0
55
777777784
40000020

注意

对于第一个测试用例,没有成对的朋友,因此所有配对的友谊值为 $$$0$$$ 并在后续轮次中保持 $$$0$$$,因此所有游览的友谊值为 $$$0$$$。

对于第二个测试用例,只有一对可能的 $$$(1, 2)$$$,其友谊值最初为 $$$1$$$,因此每轮都会选择它们,并且他们的友谊值会增加 $$$1$$$。因此,总和为 $$$1+2+3+\ldots+10 = 55$$$。

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