一个班有$$$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)$$$。