#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5,mod=1e9+7;
int n,m,t,ans,ok,pos[N],a[N],v,tot,d[13],b[13],okk; 
int ksm(int x,int y){
	int cnt=1;
	while(y){
		if(y&1) cnt=cnt*x%mod;
		x=x*x%mod; y>>=1;
	}
	return cnt;
}
void sol1(){
	ans=ksm((v*v%mod-v+1+mod)%mod,n-1);
	printf("%lld\n",ans);
}
void sol2(){
	ans=ksm(v*v%mod,n-1);
	printf("%lld\n",ans);
}
void dfs(int pos){
	if(pos>=n){++ans;return;}
	for(int i=0;i<4;i++){
		int tem=b[pos],tem2=b[pos+1]; 
		if(b[pos]){
			if(b[pos]==(((i>>1)&1)+1)&&b[pos+1]&&b[pos+1]!=(i&1)+1) continue;
			else if(b[pos]==(((i>>1)&1)+1)) b[pos+1]=(i&1)+1;
		}
		dfs(pos+1);
		b[pos]=tem,b[pos+1]=tem2;
	}
}
void sol3(){
	ans=0;
	for(int i=0;i<=n;i++) b[i]=d[i];
	dfs(1);
	printf("%lld\n",ans%mod);
}
signed main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%lld",&t);
	while(t--){
		scanf("%lld%lld%lld",&n,&m,&v); ok=okk=0;
		if(n<=12&&m<=12&&v<=2) memset(d,0,sizeof d);
		for(int i=1;i<=m;i++){
			scanf("%lld%lld",&pos[i],&a[i]);
			if(pos[i]!=i) ok=1;
			if(n<=12&&m<=12&&v<=2){
				if(d[pos[i]]&&d[pos[i]]!=a[i]){
					puts("0");
					okk=1;
					break;
				}
				d[pos[i]]=a[i];
			}
		}
		if(okk) continue;
		if(!ok&&n==m) sol1();
		else if(m==1) sol2();
		else if(n<=12&&m<=12&&v<=2) sol3();
	}
	return 0;
}
/*
1
89793 1 22228
59585 13402
*/
