#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e5 + 7;
const int mod = 1e9 + 7;
int T;
int n, m, k;
int c[maxn], d[maxn];
long long qp(long long a, long long b) {
	long long sum = 1;
	a %= mod;
	while(b) {
		if(b & 1) sum = sum * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return sum % mod;
}
signed main() {
	freopen("assign.in", "r", stdin);
	freopen("assign.out", "w", stdout);
	scanf("%lld", &T);
	while(T--) {
		scanf("%lld%lld%lld", &n, &m, &k);
		for(int i = 1; i <= m; i++) {
			int u, v;
			scanf("%lld%lld", &u, &v);
//			if(a[u] && a[u])
//			a[u] = v;
		}
		if(m == 1)printf("%lld\n", qp(k * k % mod, n - 1));
		else if(m == n){
			long long ans = qp(((k - 1) * k % mod + 1) % mod, n - 1);
			printf("%lld\n", ans % mod);
		} else {
			printf("0\n");
		}
	}
	return 0;
}
