#include<bits/stdc++.h>
using namespace std;
long long num[1000005];
long long a[1000005],b[1000005];
long long n,m,v;
long long ans;
long long MOD=1e9+7;
void dfs(long long pos){
	if(pos==n){
		for(long long i=1;i<=n;i++){
			if(num[i]==a[i]){
				if(num[i+1]!=0&&num[i+1]!=b[i]) return ;
			}
		}
		ans++;
		return;
	}
	for(long long i=1;i<=2;i++){
		for(long long j=1;j<=2;j++){
			a[pos]=i;
			b[pos]=j;
			dfs(pos+1);
			a[pos]=0;
			b[pos]=0;
		}
	}
}
long long fast(long long a,long long b,long long c){
	a%=c;
	long long res=1;
	while(b){
		if(b&1){
			res=(res*a)%c;
		}
		a=(a*a)%c;
		b>>=1;
	}
	return res;
}
signed main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	long long T;
	cin>>T;
	while(T--){
		long long f=1;
		memset(num,0,sizeof num);
		memset(a,0,sizeof a);
		memset(b,0,sizeof b);
		ans=0;
		cin>>n>>m>>v;
		if(n<=12&&m<=12&&v<=12){
			ans=0;
			for(long long i=1;i<=m;i++){
				long long c,d;
				cin>>c>>d;
				if(num[c]!=0){
					f=0;
				}
				num[c]=d;
			}
			if(f==0){
				cout<<'0'<<'\n';
				continue; 
			}
			dfs(1);
			cout<<ans<<'\n';
		}
		else if(m==1){
			ans=1;
			long long c,d;
			cin>>c>>d;
			cout<<fast(fast(v,2,MOD),n-1,MOD)<<'\n';
		}
		else cout<<"1145141919810"<<'\n';
	}
	return 0;
}

