#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int t,n,m,v;
int a[110];
int b[110],c[110];
bool abc(){
	for(int i=1;i<n;i++) if(!((a[i]!=b[i])||(a[i]==b[i]&&a[i+1]==c[i]))) return false;
	return true;
}
bool check(int x){
	if(x>n) return abc();
	if(a[x]) if(check(x+1)) return true;
	else{
		for(int i=1;i<=v;i++){
			a[x]=i;
			if(check(x+1)) return true;
		}	
	}
	return false;
}
int dfs(int x){
	if(x>=n){
		if(check(1)) return 1;
		return 0;
	}
	int sum=0;
	for(int i=1;i<=v;i++){
		for(int j=1;j<=v;j++){
			b[x]=i,c[x]=j;
			sum=(sum+dfs(x+1))%mod;
		}
	}
	return sum;
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%d",&t);
	while(t--){
		scanf("%d%d%d",&n,&m,&v);
		int x,y;
		bool flag=false;
		for(int i=1;i<=m;i++){
			scanf("%d%d",&x,&y);
			if(a[x]&&a[x]!=y) flag=true;
			a[x]=y;
		}
		if(flag) printf("0\n");
		else printf("%d\n",dfs(1)%mod);
	}
	return 0;
}
