CF1925D Good Trip

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) $ .

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

For each test case, print one integer — the answer to the problem.

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) $ .