#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5, mod = 1e9 + 7;
typedef long long LL;
int n, m, v;
int c[N], d[N];
int x[N];
LL f[N][2][2];//0 : == 1 : !=
int a[N], b[N];

long long qpow(long long a, int b) {
	long long res = 1;
	while (b) {
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res % mod;
}

void solve() {
	memset(x, 0, sizeof x);
	cin >> n >> m >> v;
	for (int i = 1; i <= m; i++) {
		cin >> c[i] >> d[i];
		if (x[c[i]] && x[c[i]] != d[i]) {
			cout << 0 << endl;
			return;
		}
		x[c[i]] = d[i];
	}
	if (v <= 2) {
		int ans = 0;
		for (int i = 0; i < (1 << n - 1); i++) {
			for (int j = 0; j < (1 << n - 1); j++) {
				for (int k = 0; k < n - 1; k++) {
					x[k + 1] = 0;
					a[k] = ((i >> k) & 1) + 1, b[k] = ((j >> k) & 1) + 1;
				}
				x[n] = 0;
				for (int k = 1; k < m; k++) {
					x[c[k]] = d[k];
				}
				bool flag = 0;
				for (int k = 0; k < n - 1; k++) {
					if (x[k + 1]) {
						if (x[k + 2]) {
							if (a[k] == x[k + 1]) {
								if (b[k] != x[k + 2]) {
									flag = 1;
									break;
								}
							}
						} else if (a[k] == x[k + 1]){
							x[k + 2] = b[k];
						}
					}
				}
				if (!flag) ans++;
			}
		}
		cout << ans << endl;
	} else if (m == n) {
		long long ans = 1;
		for (int i = 1; i <= n; i++) {
			ans = (ans + (v - 1) * v * (n - i + 1) % mod) % mod;
		}
		cout << ans << endl;
	} else {
		cout << 0 << endl;
	}
}

int main() {
	freopen("assign.in", "r", stdin);
	freopen("assign.out", "w", stdout);
	int TT;
	cin >> TT;
	while (TT--) {
		solve();
	}
	return 0;
} 
