#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int mod=1e9+7;
int T,n,m;
struct node{
	int c,d;
}a[N];
long long ans,v;
bool cmp(node q,node p){
	return q.c<p.c;
}
int A[20],B[20],x[20],y[20];
long long _pow(long long x,long long y){
	long long s=1;
	while(y){
		if(y&1) s=s*x%mod;
		x=x*x%mod,y>>=1;
	}
	return s;
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	cin>>T;
	while(T--){
		cin>>n>>m>>v;
		for(int i=1;i<=m;i++)
			scanf("%d%d",&a[i].c,&a[i].d);
		sort(a+1,a+1+m,cmp);
		ans=1;
		for(int i=2;i<=m;i++)
			if(a[i].c==a[i-1].c&&a[i].d!=a[i-1].d) ans=0;
		if(ans==0||v==1){
			printf("%lld\n",ans);
			continue;
		}
		if(n==m){
			for(int i=1;i<n;i++)
				ans*=((v-1)*v%mod+1)%mod,ans%=mod;
			printf("%lld\n",ans);
			continue;
		}
		if(v==2){
			ans=0;
			for(int i=1;i<=n;i++)
			  x[i]=0,y[i]=0;
			for(int i=1;i<=m;i++)
			  x[a[i].c]=a[i].d,y[a[i].c]=a[i].d;
			for(int i=0;i<(1<<(n-1));i++){
				int t=i;
				for(int j=1;j<n;j++){
					if(t&1) A[j]=1;
					else A[j]=2;
					t>>=1;
				}
				for(int j=0;j<(1<<(n-1));j++){
					int tmp=j,fl=1;
					for(int k=1;k<n;k++){
						if(tmp&1) B[k]=1;
						else B[k]=2;
						if(A[k]==x[k]&&x[k+1]!=0&&B[k]!=x[k+1]){
							fl=0;
							break;
						}
						tmp>>=1;
					}
					ans=(ans+fl)%mod;
				}
			}
			printf("%lld\n",ans);
			continue;
		}
		ans=(_pow(v*v,1ll*n-1)-2+mod)%mod;
		printf("%lld\n",ans);
		
	}
	return 0;
}
/*
3
2 1 2
1 1
2 2 2
1 1
2 2
2 2 2
1 1
1 2
*/
