#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int N = 1e5+3;
const int mo = 1e9+7;

int n, m, k, x[N], y[N], a[N];
ll fac[N], ifac[N], ans;
map <int, int> mp;

ll qp(ll a, int b) {
	ll s=1;
	while(b) {
		if(b & 1) s = s*a%mo;
		a = a*a%mo, b >>= 1;
	}
	return s;
}
#define inv(x) qp(x, mo-2)
void init(int n) {
	fac[0] = 1;
	for(int i=1; i <= n; ++i) fac[i] = fac[i-1]*i%mo;
	ifac[n] = inv(fac[n]);
	for(int i=n-1; ~i; --i) ifac[i] = ifac[i+1]*(i+1)%mo;
}
ll C(int n, int m) {
	if(n<m || n<0 || m<0) return 0;
	return fac[n] * ifac[n-m]%mo * ifac[m]%mo;
}

int checkA() {
	return n == m;
}
void solveA() {
	cerr << "A" << endl;
	for(int i=0; i < n; ++i) {
		ans += C(n-1, i) * qp(k, n-1-i)%mo * qp(k-1, n-1-i)%mo;
		ans %= mo;
	}
}
void solve() {
	ans=0;
	mp.clear();
	for(int i=1; i <= m; ++i) {
		if(mp[x[i]] && mp[x[i]] != y[i]) {
			puts("0");
			return ;
		}
		mp[x[i]] = y[i];
	}
	if(k <= 2) {
		cerr << "v=2" << endl;
		ans = qp(k, (n-1)*2);
	}
	else if(m == 1) ans = qp(k, (n-1)*2), cerr << "m=1" << endl;
	else if(checkA()) solveA();
	cout << ans << endl;
}
int main() {
	freopen("assign.in", "r", stdin);
	freopen("assign.out", "w", stdout);
	int TT;
	cin >> TT;
	init(100000);
//	cerr << C(5, 3) << endl;
	while(TT--) {
		cin >> n >> m >> k;
		for(int i=1; i <= m; ++i) scanf("%d%d", &x[i], &y[i]);
		solve();
	}
	return 0;
}

