#include<bits/stdc++.h>
using namespace std;

const int N=15;const long long mod=1000000000+7;
long long n,m,T,v,a[N],b[N],x[N],ans; 
long long qu(long long a,long long b){
	long long sum=1,base=a;
	while(b){
		if(b&1)sum*=base;
		base*=base;
		b>>=1;
		sum%=mod;
	}
	return sum;}
void dfs(int dep){
	if(dep==n){
		for(int i=1;i<=n-1;i++){
//			if(x[i]==a[i]&&x[i+1]!=b[i]&&x[i+1]!=0){
//				return;
//			} 
			if(x[i]==a[i]){
				if(x[i+1]!=b[i]&&x[i+1]!=0)return;
				
			}	
		}
		ans++;ans=ans%mod;
		return;
	}
	a[dep]=1;b[dep]=2;dfs(dep+1);b[dep]=1;dfs(dep+1);
	a[dep]=2;b[dep]=2;dfs(dep+1);b[dep]=1;dfs(dep+1);
	return;
}

int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	cin>>T;
	while(T--){
		cin>>n>>m>>v;
		if(v==1){cout<<1<<endl;continue;}
//		if(m==1){
//			int inx,w;cin>>inx>>w;
//			cout<<qu(v,2*n-2)%mod<<endl;
//		}
//		else{
		int fl=1;ans=0;
		for(int i=1;i<=n+1;i++)x[i]=0;
		for(int i=1;i<=m;i++){
			int inx,w;
			cin>>inx>>w;
			if((x[inx]!=0)&&(w!=x[inx])){
				fl=0;break;
			}
			x[inx]=w;
		}
		if(fl==0){cout<<0<<endl;continue;}
		dfs(1);cout<<ans<<endl;
	}
	return 0;
}
