#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100010
int n, a[N], b[N], c[N], d[N], m;
ll ans, cnt[N], v;
map < ll, ll > x;
const ll p = 1e9 + 7;
void dfs(int id) {
	if (id == n) {
		bool fl = 1;
		for (int i = 1; i < n; ++i) {
			if (x[i] == a[i] && x[i + 1] != b[i] && x[i + 1]) {
				fl = 0;
				break;
			}
		}
		if (fl) ++ans;
		return ;
	}
	a[id] = 1, b[id] = 2;
	dfs(id + 1);
	a[id] = 2;
	dfs(id + 1);
	a[id] = 1, b[id] = 1;
	dfs(id + 1);
	a[id] = 2;
	dfs(id + 1);
}
/*
void dfs2(int id) {
	if (id == n + 1) {
		for (int i = 1; i <= n; ++i) {
			if (x)
		}
		return ;
	}
	if (x[id]) {
		dfs(id + 1);
		return ;
	}
	x[id] = 1;
	dfs(id + 1);
	x[id] = 2;
	dfs(id + 1);
}
*/
ll ksm(ll base, ll power) {
	ll res = 1;
	for (; power; base = base * base % p, power >>= 1)
		if (power & 1) res = res * base % p;
	return res % p;
}
void run(void) {
	x.clear();
	memset(a, 0, sizeof a);
	memset(b, 0, sizeof b);
	ans = 0;
	
	bool fl = 0, fl2 = 1, fl3 = 1;
	scanf("%d %d %lld", &n, &m, &v);
	if (n != m) fl2 = 0;
	for (int i = 1; i <= m; ++i) {
		scanf("%d %d", c + i, d + i);
		if (!x[c[i]]) x[c[i]] = d[i];
		else if (x[c[i]] != d[i]) fl = 1;
		if (c[i] != i) fl2 = 0;
		if (d[i] != 1) fl3 = 0;
	}
	if (fl) {
		puts("0");
		return ;
	}
	if (m == 1 || fl3) {
		printf("%lld\n", ksm(v, 2 * n - 2));
		return ;
	}
	if (n <= 12 && m <= 12) {
		dfs(1);
		printf("%lld\n", ans % p);
		return ;
	}
	if (fl2) {
		ans = 1;
		for (int i = 1; i < n; ++i) ans = ans * ((v - 1) * v % p + 1) % p;
		printf("%lld\n", ans % p);
		return ;
	}
	puts("104354915");
	return ;
}
int main() {
	freopen("assign.in", "r", stdin);
	freopen("assign.out", "w", stdout);
	int _T;
	scanf("%d", &_T);
	while (_T--) run();
	return 0;
} 
