#include <bits/stdc++.h>
#define USE_FREOPEN
#define MUL_TEST
#define FILENAME "assign"
#define int long long

const int N = 1e5 + 5, mod = 1e9 + 7;
int n, m, v, c[N], d[N]; 
std::unordered_map<int, int> set;
int f[N][105], ans;

void dfs(int u) {
	if (u == n) {
		++ans;
		return;
	}
	for (int a = 1; a <= 2; ++a) {
		for (int b = 1; b <= 2; ++b) {
			if (set[u] && set[u] == a && set[u + 1] && b != set[u + 1]) continue;
			dfs(u + 1);
		}
	}
}

void solve() {
	scanf("%lld%lld%lld", &n, &m, &v);
	bool flag_a = 1;
	for (int i = 1; i <= m; ++i) scanf("%lld%lld", &c[i], &d[i]), flag_a &= (c[i] == i);
	for (int i = 1; i <= m; ++i) {
		if (set[c[i]] && set[c[i]] != d[i]) {
			puts("0");
			return;
		}
		set[c[i]] = d[i];
	}
	if (n == m && flag_a) {
		int x = (1 + (v - 1) * v % mod) % mod;
		for (int i = 2; i < n; ++i) x = (x *  (1 + (v - 1) * v % mod)) % mod;
		printf("%lld\n", x);
	}
	else if (v <= 2) {
		dfs(1);
		printf("%lld\n", ans);
	}
}

signed main() {
#ifdef USE_FREOPEN
	freopen(FILENAME ".in", "r", stdin);
//	freopen(FILENAME ".out", "w", stdout);
#endif

	int _ = 1;
#ifdef MUL_TEST
	scanf("%lld", &_);
#endif
	while (_--) solve();
	_ ^= _;
	return (0^_^0);
}


