D. Хорошее путешествие
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В классе есть $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — ответ на задачу.

Пример
Входные данные
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
Выходные данные
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)$$$.