#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define ld long double
using namespace std;
const int N=20+10,mod=1e9+7;
int t,n,m,v,x[N],a[N],b[N]; 
inline void solve(){
	memset(x,0,sizeof(x));
	int flag=1;
	cin>>n>>m>>v;
	int ans=0;
	for(int i=1;i<=m;i++){
		int c,d;
		cin>>c>>d;
		if(x[c]&&x[c]!=d) flag=0;
		x[c]=d;
	}
	if(!flag){
		cout<<0<<endl;
		return;
	}
	if(v==1){
		cout<<1<<endl;
		return;
	}
	for(int s1=0;s1<(1<<n-1);s1++){
		for(int s2=0;s2<(1<<n-1);s2++){
			for(int i=1;i<n;i++){
				if(s1&(1<<i-1)) a[i]=1;
				else a[i]=2;
				if(s2&(1<<i-1)) b[i]=1;
				else b[i]=2;
			}
			int p=0,flag=1;
			for(int i=1;i<=n;i++){
				if(x[i]&&p&&x[i]!=p) flag=0;
				if(p&&p==a[i]) p=b[i];
				else if(x[i]&&x[i]==a[i]) p=b[i];
				else p=0;
			}
			ans+=flag;
			ans%=mod;
		} 
	}
	cout<<ans<<endl;
}
signed main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	while(t--) solve();
	return 0;
}

