#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 50, mod = 1e9 + 7;
int T, n, m, v, c[maxn], d[maxn], a[maxn], b[maxn], num[maxn], x[maxn], ans;
//vector<int> v[maxn];

bool check() {
	int state = (1 << n);
	for(int i = 0; i < state; i++) {
		int flag = 1;
		for(int j = 1; j <= n; j++) {
			if(num[j] == 0) x[j] = ((i >> (j - 1)) & 1) + 1;
			else x[j] = num[j];
		}
		for(int j = 1; j < n; j++) {
			if(x[j] == a[j] && x[j + 1] != b[j]) {
				flag = 0;
				break;
			}
		}
		if(flag) return 1;
	}
	return 0;
}

void dfs(int dep) {
	if(dep >= n) {
//		for(int i = 1; i < n; i++) cout << a[i] << ' ' << b[i] << endl;
		if(check()) ans++;
		return ;
	}
	int i = dep;
	a[i] = b[i] = 1;
	dfs(dep + 1);
	a[i] = b[i] = 2;
	dfs(dep + 1);
	b[i] = 1, a[i] = 2;
	dfs(dep + 1);
	a[i] = 1, b[i] = 2;
	dfs(dep + 1);
	a[i] = b[i] = 0;
}

void solve() {
	ans = 0;
	dfs(1);
	cout << ans << '\n';
}

int ksm(int x, int y){
	int res = 1;
	while(y){
		if(y & 1) res = res * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}

void solve2(){
	cout << ksm(v, n - 1) * (v - 1) % mod << '\n';
}

signed main() {
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin >> T;
	while(T--) {
		cin >> n >> m >> v;
		bool f = 1;
		for(int i = 1; i <= 12; i++) num[i] = 0;
		for(int i = 1; i <= m; i++) {
			cin >> c[i] >> d[i];
			if(num[c[i]] == 0 || num[c[i]] == d[i]) num[c[i]] = d[i];
			else{
				cout << "0\n";
				f = 0;
				break;
			}
		}
		if(v <= 2 && f) solve();
		else solve2();
	}
	return 0;
}
/*
3
2 1 2
1 1
2 2 2
1 1
2 2
2 2 2
1 1
1 2

1
2 2 2
1 1
1 2

5
5 1 2
1 2
6 5 2
4 2
5 1
4 2
2 2
2 1
7 1 2
4 1
10 11 2
10 2
7 2
7 2
2 2
3 2
4 2
10 2
7 2
10 2
3 2
3 2
12 2 2
7 2
7 2


256
0
4096
129600
4194304
*/
