#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const ll P=1e9+7;
int a[20],t1[20],t2[20];
ll ans;
int n,m;
ll v;
void dfs(int x){
	if(x==n){
		int b[20];
		for(int i=1;i<=n;i++){
			b[i]=a[i];
		}
		for(int i=1;i<n;i++){
			if(b[i]!=t1[i]) continue;
			if(b[i]==t1[i]){
				if(b[i+1]>0 && b[i+1]!=t2[i]){
					return;
				}
				if(b[i+1]==0){
					b[i+1]=t2[i];
				}
			}
		}
		ans++;
		ans%=P;
		return;
	}
	t1[x]=1,t2[x]=1;
	dfs(x+1);
	t1[x]=2,t2[x]=1;
	dfs(x+1);
	t1[x]=1,t2[x]=2;
	dfs(x+1);
	t1[x]=2,t2[x]=2;
	dfs(x+1);
}
ll ksm(int a,int b){
	ll res=1;
	ll tt=a;
	ll t=1;
	if(b&1){
		res=a;
		b-=1;
	}
	while(b){
		tt*=tt;
		tt%=P;
		if(b&(1<<t)){
			res*=tt;
			res%=P;
			b-=(1<<t);
		}
		t++;
	}
	return res%P;
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T--){
		ans=0;
		scanf("%d%d%lld",&n,&m,&v);
		if(v<=2){
			memset(a,0,sizeof(a));
			bool has=0;
			for(int i=0;i<m;i++){
				int u,vv;
				scanf("%d%d",&u,&vv);
				if(a[u] && a[u]!=vv){
					has=1;
				}
				a[u]=vv;
			}
			if(has){
				printf("0\n");
				continue;
			}
			dfs(1);
			printf("%lld\n",ans%P);
		}
		else{
			int u,vv,last=-1;
			bool has=0;
			for(int i=0;i<m;i++){
				scanf("%d%d",&u,&vv);
				if(last==-1){
					last=vv;
				}else{
					if(last!=vv){
						has=1;
					}
				}
			}
			if(has){
				printf("0\n");
				continue;
			}
			printf("%lld\n",ksm(v,n*2-2));
		}
	}
	return 0;
}
