#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;
#define mp make_pair
#define fi first
#define se second
template < typename T > void read(T &x) {
	x = 0; char s = getchar(); bool f = 0;
	while (! isdigit(s)) { f |= s == '-'; s = getchar(); }
	while (isdigit(s)) { x = x * 10 + s - 48; s = getchar(); }
	x = f ? -x : x;
}

const int MAXN = 1e5 + 7;

const ll Mod = 1e9 + 7;

ll n, m, v;

struct Node {
	ll c, d;
	bool operator < (const Node other) const {
		return c < other.c;
	}
} A[MAXN];

ll qpow(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1) ans = ans * a % Mod;
		a = a * a % Mod; b >>= 1;
	}
	return ans;
}

ll ans = 0, a[MAXN];

pair < int, int > Ans[MAXN];

bool check() {
	for (int i = 1; i < n; i ++) 
		if (a[i]) 
			if (Ans[i].fi == a[i] && a[i + 1] &&  a[i + 1] != Ans[i].se) return false;
	return true;
}

void dfs(int u) {
	if (u >= n) {
		if (check()) ans ++;
		return ;
	} 
	for (int i = 1; i <= v; i ++)
		for (int j = 1; j <= v; j ++)
			Ans[u] = mp(i, j), dfs(u + 1);
}

void Solve2() {
	memset(a, 0, sizeof(a)); ans = 0;
	for (int i = 1; i <= m; i ++) {
		int u, k; read(u); read(k);
		if (a[u] && a[u] != k) {
			cout << 0 << '\n';
			return ;
		}
		a[u] = k;
	}	
	dfs(1);
	cout << ans << '\n';
}

void Solve() {
	read(n); read(m); read(v);
	if (n <= 10) { Solve2(); return; }
	ll flag = 0;
	for (int i = 1; i <= m; i ++) read(A[i].c), read(A[i].d);
	sort(A + 1, A + 1 + m);
	for (int i = 1; i < m; i ++) 
		if (A[i].c == A[i + 1].c && A[i].d == A[i + 1].d) continue;
		else if (A[i].c + 1 == A[i + 1].c) flag ++;
		else if (A[i].c == A[i + 1].c && A[i].d != A[i + 1].d) { cout << 0 << '\n'; return ; }
	cout << qpow(v * v % Mod, n - 1 - flag) * qpow(v * (v - 1) + 1, flag) % Mod << '\n';
}

int main () {
	freopen("assign.in", "r", stdin);
	freopen("assign.out", "w", stdout);
	int T; read(T);
	while (T --) Solve();
	return 0;
}
/*
3
2 1 2
1 1
2 2 2
1 1
2 2
2 2 2
1 1
1 2

10 11 2
2 2
3 2
4 2
7 2
10 2

7 1 2
4 1
*/
