#include <iostream>
#include <cstring>
#include <unordered_map>
using namespace std;
const int mod = 1e9 + 7, N = 500010;
int c[N], d[N];
int n, m, v;
unordered_map<int, int> a, aa;
int qmi(long long a, long long k){
	int res = 1;
	while (k){
		if(k & 1) res = (long long)res * a % mod;
		a = (long long)a * a % mod;
		k >>= 1;
	}
	return res;
}
int ans = 0;
int asdfs = 0;
bool check(){
	aa = a;
	for (int i = 1; i < n; i ++ ){
		if(aa.find(i) != aa.end()){
			if(aa[i] == c[i]){
				if(aa.find(i + 1) != aa.end() && aa[i + 1] != d[i]){
					return false;
				}
				aa[i + 1] = d[i];
			}
		}
	}
	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 ++ ){
			c[u] = i, d[u] = j;
			dfs(u + 1);
		}
}
int main(){
	freopen("assign.in", "r", stdin);
	freopen("assign.out", "r", stdin);
	int T;
	cin >> T;
	while (T -- ){
		cin >> n >> m >> v;
//		cout << n << ' ' << m << ' ' << v << '\n';
		a.clear();
		bool cf = 0, flag = 0;
		for (int i = 1; i <= m; i ++ ){
			int c, d;
			cin >> c >> d;
			if(a.find(c) != a.end()){
				cf = 1;
				if(a[c] != d){
					flag = 1;
					break;
				}
			}
			a[c] = d;
		}
		if(flag){
			puts("0");
			goto end;
		}
		if(n == m && !cf){
			cout << qmi((long long)v * (v - 1) + 1, n - 1) << '\n';
			goto end;
		}else if(m == 1){
			cout << qmi(v, 2 * (n - 1)) << '\n';
			goto end;
		}else if(n <= 12 && v <= 2){
			ans = 0;
			dfs(1);
			cout << ans << '\n';
		}
		
		
		
		end:;
	}
}
//1
//10 11 2
//10 2
//7 2
//7 2
//2 2
//3 2
//4 2
//10 2
//7 2
//10 2
//3 2
//3 2

