#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int mod=1e9+7;
int T,n,m,v,c[N],d[N];
int x[N],a[35],b[35],x2[N];
long long qpow(int p,int q){
	if(q==1) return p;
	long long temp=qpow(p,q/2);
	if(q%2==0) return (temp*temp)%mod;
	else return ((temp*temp)%mod*p)%mod;
}
int main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%d",&T);
	while(T--){
		memset(x,0,sizeof(x));
		scanf("%d%d%d",&n,&m,&v);
		long long ans=0;
		for(register int i=1;i<=m;i++)
			 scanf("%d%d",&c[i],&d[i]);
		if(m==1){
			printf("%lld\n",qpow(v,2*n-2));
			continue;
		}
		if(v<=2){
			bool flag=true;
			for(register int i=1;i<=m;i++){
				if(x[c[i]]!=0 && x[c[i]]!=d[i]) flag=false;
				x[c[i]]=d[i];
			}
			if(!flag){
				printf("0\n");
				continue;
			}
			for(register int i=0;i<pow(2,n-1);i++){
				int l=i,sum=0;
				while(l){
					a[++sum]=(l%2)+1;
					l/=2;
				}
				for(register int j=sum+1;j<n;j++)
					a[j]=1;
				for(register int j=0;j<pow(2,n-1);j++){
					int l2=j,ct=0;
					while(l2){
						b[++ct]=(l2%2)+1;
						l2/=2;
					}
					for(register int k=ct+1;k<n;k++)
						b[k]=1;
					bool f=true;
					for(register int k=1;k<=n;k++) x2[i]=x[i];
					for(register int k=1;k<n;k++){
						if(x[k]==a[k] && x[k+1]==0) x[k+1]=b[k];
						else if(x[k]==a[k] && x[k+1]!=b[k]){
							f=false;
						}
						if(!f) break;
					}
					for(register int k=1;k<=n;k++) x[i]=x2[i];
					if(f) ans++,ans%=mod;
				}
			}
			printf("%lld\n",ans);
		}
	}
	return 0;
}
/*5
5 1 2
1 2
6 5 2
4 2
5 1
4 2
2 2
2 1
7 1 2
4 1
10 11 2
10 2
7 2
7 2
2 2
3 2
4 2
10 2
7 2
10 2
3 2
3 2
12 2 2
7 2
7 2*/
