#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
int t, n, m, v, ans, c[10005], d[10005];
int a[10005], p[10005][2], l[10005];
bool check(){
	for(int i = 1; i <= n; i++){
		l[i] = a[i];
	}
	for(int i = 1; i < n; i++){
		if(l[i] == p[i][0]){
			if(l[i + 1] && l[i + 1] != p[i][1])return false;
			l[i + 1] = p[i][0];
		}
	}
	return true;
}
void dfs(int now){
	if(now == n){
		if(check())ans++;
		ans %= mod;
		return;
	}
	for(int i = 1; i <= v; i++){
		p[now][0] = i;
		for(int j = 1; j <= v; j++){
			p[now][1] = j;
			dfs(now + 1);
		}
		
	}
}
signed main(){
	freopen("assign.in", "r", stdin);
	freopen("assign.out", "w", stdout);
	scanf("%lld", &t);
	while(t--){
		scanf("%lld%lld%lld", &n, &m, &v);
		ans = 0;
		bool f = 0;
		for(int i = 1; i <= n; i++)a[i] = 0;
		for(int i = 1; i <= m; i++){
			scanf("%lld%lld", c + i, d + i);
			if(a[c[i]] && a[c[i]] != d[i])f = 1;
			a[c[i]] = d[i];
		}
		if(f){
			printf("0\n");
			continue;
		}
		dfs(1);
		printf("%lld\n", ans);
	}
	return 0;
}
