//assign
#include<bits/stdc++.h>
using namespace std;
long long mo, b[20];
struct node{
	int c, d;
}a[100010];
bool cmp(node x, node y) {
	return x.c < y.c;
}
long long ksm(long long x, long long y) {
	if (y == 0) return 1;
	long long res = 1;
	while (y > 1) {
		if (y % 2 == 1) res = res * x % mo;
		x = x * x % mo, y /= 2;
	}
	return res * x % mo;
}
bool check(int x, int y, int n) {
	for (int i = 1; i <= n; i++) {
		int u = x % 2, v = y % 2;
		x /= 2, y /= 2;
		if (b[i + 1] != 0 && b[i] == x + 1 && b[i + 1] != y + 1)
		    return false;
	}
	return true;
}
int main() {
	freopen("assign.in", "r", stdin);
	freopen("assign.out", "w", stdout);
	mo = 1000000007;
	int T; scanf("%d", &T);
	while (T--) {
		long long n, m, v; scanf("%lld%lld%lld", &n, &m, &v);
		for (int i = 1; i <= m; i++)
		    scanf("%d%d", &a[i].c, &a[i].d);
		if (m == 1) {
			printf("%lld\n", ksm(v, 2 * n - 2));
			continue;
		}
		sort(a + 1, a + m + 1, cmp);
		long long ans = 0, zs = 0;
		bool flag = true, lx = true;
		int last = a[1].c;
		for (int i = 2; i <= m; i++) {
			if (a[i].c == a[i - 1].c && a[i].d != a[i - 1].d) {
				flag = false; break;
			}
			if (last + 1 != a[i].c) lx = false;
			last = a[i].c;
		}
		if (!flag) {printf("0\n"); continue;}
		if (lx) {printf("%lld\n", ksm(v * (v - 1) % mo + 1, n - 1)); continue;}
		for (int i = 1; i <= m; i++) b[a[i].c] = a[i].d;
		for (int i = 0; i < (1 << (n - 1)); i++)
		    for (int j = 0; j < (1 << (n - 1)); j++)
		    	if (check(i, j, n)) {
		    		//if (id == 4) printf("%d %d\n", i, j);
		    		ans++;
				}
		printf("%d\n", ans);
		for (int i = 1; i <= n; i++) b[i] = 0;
	}
	return 0;
}
