#include <cstdio>
#define ll long long
using namespace std;
const int N=1e6+5, Mod=1e9+7;
int t, n, m, v, val[N], a[N], b[N];
ll ans;
void dfs(int x){
	if(x >= n){
		bool flag = true;
		for(int i=1; i<n; ++i)
			if(val[i]==a[i] && val[i+1]!=b[i]){
				if(val[i+1] == v+1) val[i+1] = b[i];
				else{
					flag=false; break;
				}
			}
		if(flag) ++ans;
		return;
	}
	for(int i=1; i<=v; ++i)
		for(int j=1; j<=v; ++j){
			a[x]=i, b[x]=j;
			if(val[x] == i){
				if(val[x+1] == v+1){
					val[x+1] = j;
					dfs(x+1);
					val[x+1] = v+1;
				}
				else if(val[x+1] == j) dfs(x+1);
			}
			else dfs(x+1);
		}
}
inline void solve(){
	ans = 0;
	scanf("%d%d%d", &n, &m, &v);
	bool flag = true;
	if(n < N){
		for(int i=1; i<=n; ++i) val[i] = v+1;
	}
	for(int i=1,c,d; i<=m; ++i){
		scanf("%d%d", &c, &d);
		if(c<N && val[c]!=v+1 && val[c]!=d)
			flag = false;
		if(c < N) val[c] = d;
	}
	if(!flag){
		printf("0\n"); return;
	}
	if(n<=12 && v<=2){
		dfs(1);
		printf("%lld\n", ans);
		return;
	}
	else if(m == n){
		ans = 1;
		for(int i=1; i<n; ++i){
			ans = ans*((1ll*v*v%Mod-v+1)%Mod+Mod)%Mod;
		}
		printf("%lld\n", ans);
		return;
	}
	printf("0\n");
}
int main(){
	freopen("assign.in", "r", stdin);
	freopen("assign.out", "w", stdout);
	scanf("%d", &t);
	while(t--) solve();
	fclose(stdin);
	fclose(stdout);
	return 0;
}
