#include<bits/stdc++.h> #define debug(x) cout << #x << ":\t" << (x) << endl; usingnamespace std; #define ll long long constint N = 2e6 + 10; constint INF = 0x3f3f3f3f; const ll inf = 0x3f3f3f3f3f3f3f3f; const ll mod = 1e9 + 7; int T; int n, m, k; vector<int>G[N]; int f[N][30], dep[N]; voiddfs(int u, int _fa){ f[u][0] = _fa; dep[u] = dep[_fa] + 1; for (int i = 1; (1 << i) <= dep[u]; i++) f[u][i] = f[f[u][i - 1]][i - 1]; for (int v : G[u]) { if (v != _fa)dfs(v, u); } } intLCA(int u, int v){ if (dep[u] < dep[v])swap(u, v); for (int i = 20; i >= 0; i--) { if ((1 << i) <= dep[u] - dep[v]) u = f[u][i]; } if (v == u)return u; for (int i = 20; i >= 0; i--) { if (f[u][i] != f[v][i]) { u = f[u][i]; v = f[v][i]; } } return f[u][0]; } ll fac[N], inv[N]; ll power(ll a, int x){ ll ans = 1; while (x) { if (x & 1) ans = (ans * a) % mod; a = (a * a) % mod; x >>= 1; } return ans; } voidinit(){ fac[0] = 1; for (int i = 1; i < N; i++) { fac[i] = fac[i - 1] * i %mod; } inv[N - 1] = power(fac[N - 1], mod - 2); for (int i = N - 2; i >= 0; i--) { inv[i] = inv[i + 1] * (i + 1) % mod; } } ll C(int n, int k){ if (n < k)return0; return fac[n] * inv[k] % mod*inv[n - k] % mod; } int d[N], cnt[N]; voiddfs2(int u, int _fa){ for (int v : G[u]) { if (v == _fa)continue; dfs2(v, u); d[u] += d[v]; } } intmain(){ init(); scanf("%d", &T); while (T--) { scanf("%d%d%d", &n, &m, &k); for (int i = 1; i <= n; i++) { G[i].clear(); d[i] = 0; cnt[i] = 0; for (int j = 0; j <= 20; j++)f[i][j] = 0; } for (int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u); } dfs(1, 0); for (int i = 0; i < m; i++) { int u, v; scanf("%d%d", &u, &v); d[u]++; d[v]++; int lca = LCA(u, v); d[lca]--; d[f[lca][0]]--; cnt[lca]++; } dfs2(1, 0); ll ans = 0; for (int i = 1; i <= n; i++) { ans = (ans + C(d[i], k) - C(d[i] - cnt[i], k) + mod) % mod; } printf("%lld\n", ans); } return0; }