#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 3, mod = 1e9 + 7;
ll n, m; ll v;
ll a[maxn], b[maxn];
map <ll, ll> mp;
ll qpow(ll a, ll b) {
	if (b < 0) return 0;
	a %= mod;
	ll res = 1;
	while (b) {
		if (b & 1) res = res * a % mod;
		a = a * a % mod, b >>= 1;
	}
	return res;
}
namespace Slv1 {
	ll s[maxn], t[maxn], d[maxn], res;
	inline bool check() {
		for (ll i = 1; i <= n; i++) d[i] = 0;
		for (ll i = 1; i <= n; i++) {
			if (d[i] && mp[i] != d[i] && mp[i] != 0) return false;
			if (!d[i]) {
				if (mp[i]) d[i] = mp[i];
				else d[i] = (s[i] == 1 ? 2 : 1);
			}
			if (d[i]) {
				if (s[i] == d[i]) d[i + 1] = t[i];
				continue;
			}
		}
		return true;
	}
	void dfs(ll c) {
		if (c == n) {
			res += check();
			return ;
		}
		for (ll i = 1; i <= v; i++)
			for (ll j = 1; j <= v; j++) {
				s[c] = i, t[c] = j;
				dfs(c + 1);
			}
	} 
	void solve() {
		res = 0;
		dfs(1);
		cout << res << '\n';
	}
}
namespace Slv2 {
	void solve() {
		cout << qpow(v, 2 * n - 2) << '\n';
	}
}
namespace Slv3 {
	void solve() {
		cout << qpow((v * (v - 1) + 1) % mod, n - 1) << '\n';
	}
}
void solve(ll id) {
	mp.clear();
	bool fl = 0, A = 1, B = 1, C = 1;
	cin >> n >> m >> v;
	if (n != m) C = 0;
	if (m != 1) B = 0;
	for (ll i = 1; i <= m; i++) {
		cin >> a[i] >> b[i];
		if (mp[a[i]] != 0 && mp[a[i]] != b[i])
			fl = 1;
		mp[a[i]] = b[i];
	}
	#define GG do {cout << "0\n"; return; } while (0)
	if (fl) GG;
	if (B) Slv2::solve();
	else if (C) Slv3::solve();
	else Slv1::solve();
}
int main() {
	freopen("assign.in", "r", stdin); 
	freopen("assign.out", "w", stdout); 
	ll T; cin >> T;
	for (ll i = 1; i <= T; i++) solve(i);
}
