#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10,mod=1e9+7;
int t,n,m,v,c[N],d[N],ans,sz[30],a[30],b[30],ans1;
struct pd{
	int a1,a2;
	bool operator <(const pd &p)const{
		return a1<p.a1;
	}
}ppd[N];
int ksm(int a,int b){
	int ans=1;
	while(b){
		if(b&1){
			ans*=a;
			if(ans>=mod)ans%=mod;
		}
		a*=a;if(a>=mod)a%=mod;
		b>>=1;
	}
	return ans;
}
void solve1(){
	int mm=v*v;if(mm>mod)mm%=mod;
	ans=ksm(mm,n-1);
	printf("%lld\n",ans);
}
void dfs(int dp){
	if(dp<=n-1){
		a[dp]=1;b[dp]=1;dfs(dp+1);
		a[dp]=1;b[dp]=2;dfs(dp+1);
		a[dp]=2;b[dp]=1;dfs(dp+1);
		a[dp]=2;b[dp]=2;dfs(dp+1);
	}
	if(dp==n){
		int fg=1;
		for(int i=1;i<n;i++){
			if(sz[i]!=a[i])continue;
			else{
				if(sz[i+1]==0){
					sz[i+1]=b[i];
				}
				else{
					if(sz[i+1]!=b[i]){
						fg=0;break;
					}
				}
			}
		}
		ans1+=fg;
		for(int i=1;i<=n;i++){
			sz[i]=0;
		}
		for(int i=1;i<=m;i++){
			sz[(int)c[i]]=d[i];
		}
		return ;
	}
}
void solve2(){
	int flag=1;
	for(int i=1;i<=m;i++){
		sz[i]=0;
	}
	for(int i=1;i<=m;i++){
		if(sz[c[i]]!=0&&sz[c[i]]!=d[i]){
			flag=0;
		}
		else{
			sz[c[i]]=d[i];
		}
	}
	if(!flag){
		printf("0\n");
		for(int i=1;i<=m;i++){
			sz[i]=0;
		}
		return ;
	}
	dfs(1);
	printf("%lld\n",ans1);
	ans1=0;
}
void solve3(){
	int mm=v*(v-1)+1;if(mm>mod)mm%=mod;
	ans=ksm(mm,n-1);
	printf("%lld\n",ans);
}
signed main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%lld",&t);
	while(t--){
		scanf("%lld%lld%lld",&n,&m,&v);
		for(int i=1;i<=m;i++){
			scanf("%lld%lld",&c[i],&d[i]);
			ppd[i].a1=c[i];ppd[i].a2=d[i];
		}
		bool flag=0;
		sort(ppd+1,ppd+1+m);
		for(int i=1;i<=m;i++){
			if(ppd[i].a1==ppd[i+1].a1&&ppd[i].a2!=ppd[i+1].a2){
				flag=1;break;
			}
		}
		if(flag){
			printf("0\n");
			for(int i=1;i<=m;i++){
				ppd[i].a1=ppd[i].a2=0;
			}
			continue;
		}
		if(n<=12){
			solve2();
		}
		else if(m==1){
			solve1();
		}
		else if(m==n){
			solve3();
		}
		else{
			printf("0\n");
		} 
	}
	return 0;
} 
