考虑分别计算 \(p\) 和 \(q\)。
按照期望的定义，\(q\) 应该等于方案的总数，也就是 \(s^k\)，其中 \(s\) 表示一共有多少个不同的组。
考虑如何求 \(p\)，我们先只计算第 \(i\) 组对 \(p\) 的贡献。如果第 \(i\) 组一共被选了 \(1\) 次，那么贡献为：
\[g=f_i \times C_{k}^{1}\times (s-1)^{k-1} \]这个式子中的三个值分别表示：这个组的价值，哪 \(1\) 次选了这个组，另外 \(k - 1\) 次选了哪些组。将上式推广到选 \(j\) 次，那么有：
\[g=(f_{i}+(f_{i}+1)+\dots+(f_{i}+j-1)) \times C_{k}^{j}\times (s-1)^{k-j} \]前面的等差数列可以在线地去维护（第 \(w\) 次加上 \(f_i+w-1\)），后面的可以用组合数 & 快速幂求解。
会发现每组的贡献的后一段都和上式一样，只有 \(f\) 的值在变化。所以我们可以提公因式，把 \(f_i\) 换成 \(\sum f_i\) 即可。
会发现 \(a_i\) 和 \(b_i\) 可以忽略，因为题目对每一次选的人没有任何限制。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 4e6 + 10;
const int mod = 1e9 + 7;
inline int Qpow(int x,int k)
{
if(x == 0 || k < 0) return 0;
int res = 1;x = x % mod;
for(;k;k >>= 1)
{
if(k & 1) res = (res * x) % mod;
x = (x * x) % mod;
} return res;
}
int inv[MAXN],fac[MAXN],invfac[MAXN];
inline int C(int n,int m)
{return (fac[n] * invfac[n - m] % mod) * invfac[m] % mod;}
int t,n,m,k,a[MAXN],b[MAXN],c[MAXN],p,q;
signed main()
{
cin >> t;
inv[0] = fac[0] = invfac[0] = 1;
inv[1] = fac[1] = invfac[1] = 1;
for(int i = 2;i <= 400000;i++)
{
inv[i] = (inv[mod % i] * (mod - mod / i)) % mod;
fac[i] = (fac[i - 1] * i) % mod;
invfac[i] = (invfac[i - 1] * inv[i]) % mod;
}
while(t--)
{
cin >> n >> m >> k;
p = 0,q = n * (n - 1) / 2;
int sum = 0,s = 0;
for(int i = 1;i <= m;i++)
{
cin >> a[i] >> b[i] >> c[i];
sum = (sum + c[i]) % mod;
}
if(n == 2)
{
if(sum == 0) p = 0;
else for(int i = 1;i <= k;i++)
p = (p + sum) % mod,sum = (sum + 1) % mod;
}
else for(int i = 1;i <= k;i++)
{
s = (s + (sum + (i - 1) * m)) % mod;
int f = (s * C(k,i) % mod) * Qpow(q - 1,k - i) % mod;
p = (p + f) % mod;
}
q = Qpow(q,k);
cout << (p * Qpow(q,mod - 2)) % mod << endl;
}
return 0;
}