#include<bits/stdc++.h>
using namespace std;
const int N=1e6+3,M=1e5+3,mod=1e9+7;
bool flag;
int T,n,m,v;
long long ans;
int a[N],t[N],c[M],d[M];
bool vv[15][15][15],vis[15][5][5];
int in(){
	int f=1,ans=0;
	char c=getchar();
	while(!isdigit(c)){
		if(c==45)
			f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		ans=ans*10+c-48;
		c=getchar();
	}
	return f*ans;
}
void dfs(int x){
	if(x>n){
		for(int i=1;i<n;++i)
			if(!vv[i][t[i]][t[i+1]]){
				vis[i][t[i]][t[i+1]]=1;
				for(int j=1;j<=v;++j)
					if(j!=t[i])
						for(int k=1;k<=v;++k)
							vis[i][j][k]=1;
				vv[i][t[i]][t[i+1]]=1;
			}
		return;
	}
	if(a[x]){
		t[x]=a[x];
		dfs(x+1);
	}
	else{
		for(int i=1;i<=v;++i){
			t[x]=i;
			dfs(x+1);
		}
	}
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	T=in();
	while(T--){
		n=in(),m=in(),v=in();
		for(int i=1;i<=n;++i)
			a[i]=0;
		flag=0;
		for(int i=0;i<m;++i){
			c[i]=in(),d[i]=in();
			if(a[c[i]]&&a[c[i]]!=d[i])
				flag=1;
			a[c[i]]=d[i];
		}
		if(flag){
			printf("0\n");
			continue;
		}
		ans=1;
		if(n<=12&&v<=12){
			memset(vv,0,sizeof(vv));
			memset(vis,0,sizeof(vis));
			dfs(1);
			long long tot;
			for(int i=1;i<n;++i){
				tot=0;
				for(int j=1;j<=v;++j)
					for(int k=1;k<=v;++k)
						if(vis[i][j][k])
							++tot;
				ans*=tot;
				ans%=mod;
			}
		}
		else{
			for(int i=1;i<n;++i){
				ans*=1+(v*(v-1));
				ans%=mod;
			}
		}
		printf("%lld\n",ans%mod);
	}
	return 0;
}
/*
256
0
4096
129600
4194304
503279958
748525720
892897109
174281099
418965370

*/
