#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
long long t, n, m, v, c[100005], d[100005], ans, x[1000005];
bool vis[4500000];
bool checkA(){
	if (m != n){
		return 0;
	}
	for (int i = 1; i <= m; ++i){
		if (c[i] != i){
			return 0; 
		} 
	}
	return 1;
}
long long fp(long long a, long long b){
	long long res = 1;
	while(b){
		if (b & 1){
			res *= a;
			res %= mod;
		}
		a *= a;
		a %= mod;
		b >>= 1;
	}
	return res;
}
void dfs2(int now, int sum){
	if (now == (n - 1) * 2 + 1){
		if (!vis[sum]){
			++ans;
			vis[sum] = 1;
		}
		return;
	}
	for (int i = 1; i <= 2; ++i){
		dfs2(now + 1, (sum << 1) + i - 1);
	}
}
void dfs(int now){
	if (now == n + 1){
		dfs2(1, 0);
		return;
	}
	if (x[now] == 0){
		for (int i = 1; i <= 2; ++i){
			x[now] = i;
			dfs(now + 1);
			x[now] = 0;
		}
	}
	else{
		dfs(now + 1);
	}
	return;
}

int 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--){
		memset(x, 0, sizeof(x));
		memset(vis, 0, sizeof(vis));
		cin >> n >> m >> v;
		map<int, int> mp;
		int flag = 1;
		for (int i = 1; i <= m; ++i){
			cin >> c[i] >> d[i];
			if (mp.find(c[i]) != mp.end() && mp[c[i]] != d[i]){
				if (!flag){
					continue;
				}
				cout << "0\n";
				flag = 0;
			}
			mp[c[i]] = d[i];
			if (c[i] <= 1000000){
				x[c[i]] = d[i];
			}
		}
		if (!flag){
			continue;
		}
		if(checkA()){
			long long a = (long long)v * v - v + 1, ans = 1;
			ans = (fp(a, n - 1) + mod) % mod;
			cout << ans << "\n";
			continue;
		}
		else if (m == 1){
			long long a = (long long)v * v, ans = 1;
			ans = (fp(a, n - 1) + mod) % mod;
			cout << ans << "\n";
			continue;
		}
		else if (n <= 12 && v == 2){
			ans = 0;
			dfs(1);
			cout << ans << "\n";
		}
	}
	return 0;
}
