B'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 <= t <= 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 <= n <= 10^5 , 0 <= m <= min Big(10^5 , frac{n(n-1)}{2} Big) , 1 <= k <= 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 <= a_i,b_i <= n , 1 <= f_i <= 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 friend'...