#include <bits/stdc++.h>
#define ll long long

using namespace std;

const ll N = 1e5, mod = 1e9 + 7;

struct node {
	ll pos, val;
	bool operator<(const node& othr) const {
		return pos < othr.pos;
	}
} c[N + 5];
ll n, m, v, a[N + 5], b[N + 5], ans;
bool flag;

void dfs1(ll t, ll now, ll x) {
	if (flag) return;
	if (t > n) {
		flag = true;
		return;
	}
	if (c[now].pos == t) {
		if (a[t - 1] == x && c[now].val != b[t - 1]) return;
		dfs1(t + 1, now + 1, c[now].val);
	}
	else if (a[t - 1] == x) dfs1(t + 1, now, b[t - 1]);
	else {
		for (ll i = 1; i <= v; i++) {
			dfs1(t + 1, now, i);
		}
	}
}

void dfs(ll t) {
	if (t >= n) {
		flag = false;
		dfs1(1, 1, 2147483647);
		ans += flag; 
		return;
	}
	for (ll i = 1; i <= v; i++) {
		for (ll j = 1; j <= v; j++) {
			a[t] = i, b[t] = j;
			dfs(t + 1);
		}
	}
}

ll qpow(ll a, ll x) {
	ll res = 1;
	while (x) {
		if (x & 1) res = res * a % mod;
		a = a * a % mod;
		x >>= 1;
	}
	return res;
}

int main() {
	freopen("assign.in", "r", stdin);
	freopen("assign.out", "w", stdout);
	ll T; scanf("%lld", &T);
	while (T--) {
		ans = 0;
		scanf("%lld%lld%lld", &n, &m, &v);
		for (ll i = 1; i <= m; i++) 
			scanf("%lld%lld", &c[i].pos, &c[i].val);
		if (m == 1) {
			printf("%lld\n", qpow(v * v % mod, n - 1));
			continue;
		}
		sort(c + 1, c + m + 1);
		if (m == n) {
			bool f = false;
			for (int i = 1; i <= m; i++) {
				if (c[i].pos != i) {
					f = true;
					break;
				}
			}
			if (!f) {
				printf("%lld\n", qpow((v - 1) * v + 1, n - 1));
				continue;
			}
		}
		bool f = false;
		for (ll i = 1; i < m; i++)
			if (c[i].pos == c[i + 1].pos) {
				f = true;
				puts("0");
				break;
			}
		if (f) continue;
		dfs(1);
		printf("%lld\n", ans);
	}
}
