#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int ma = 130 + 10,mod = 1e9 + 7;
int n,m,v,a[ma],b[ma],ans;
map <int,int> t,s;
bool check() {
	for(int i = 1; i < n; i++) {
		if(s[i] == a[i]) {
			if(s[i+1] != b[i]) {
				return 0;
			}
		}
	}
	return 1;
}
bool cal(int k) {
	if(k > n) {
		return check();
	}
	if(!t[k]) {
		for(int i = 1; i <= v; i++) {
			s[k] = i;
			if(cal(k+1)) {
				return 1;
			}
		}
	} else {
		return cal(k+1);
	}
	return 0;
}
void dfs(int k) {
	if(k >= n) {
		ans += cal(1);
		return;
	}
	for(int i = 1; i <= v; i++) {
		a[k] = i;
		for(int j = 1; j <= v; j++) {
			b[k] = j;
			dfs(k+1);
		}
	}
}
ll qpow(ll a,int mi) {
	ll ans = 1;
	while(mi) {
		if(mi&1)ans = ans * a % mod;
		a = a * a % mod;
		mi >>= 1;
	}
	return ans;
}
int main() {
	ios::sync_with_stdio(0),ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	int T;
	cin >> T;
	while(T--) {
		t.clear(),s.clear();
		ans = 0;
		int tot = 0;
		cin >> n >> m >> v;
		bool flag = 0;
		for(int i = 1,c,d; i <= m; i++) {
			cin >> c >> d;
			if(m == 1)continue;
			if(t[c] && s[c] != d)flag = 1;
			if(!t[c])tot++;
			t[c] = 1;
			s[c] = d;
		}
		if(flag) {
			cout << "0\n";
			continue;
		}
		if(m == 1) {
			cout << qpow(v,(n-1) * 2) << endl;
			continue;
		}
		dfs(1);
		cout << ans << endl;
	}
	return 0;
}
