#include<iostream>
#include<cstdlib> 
#define N 100005
using namespace std;
const int mo=1e9+7;
int T,n,m,v,ans;
int a[N],ck[N];
bool flag=0;
bool check(int ai,int bi,int i){
	if(ck[i]!=ai){
		return 1;
	}
	else{
		if(ck[i+1]==bi||ck[i+1]==0){
			ck[i+1]=bi;
			return 1;
		}
	}
	return 0;
}
bool allcheck(int cn){
	for(int i=1;i<=n;i++){
		ck[i]=a[i];
	}
	for(int i=0;i<2*n;i+=2){
		if(!check(1+((1<<i)&cn),1+((1<<i+1)&cn),(i/2)+1)){
			return 0;
		}
	}
	return 1;
}
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<=n;i++)a[i]=0;
		flag=0;
		ans=0;
		for(int i=1;i<=m;i++){
			if(flag)continue;
			int x,y;
			cin>>x>>y;
			if((a[x]==0 || a[x]==y) && x!=n){
				a[x]=y;	 
				//ans=(ans+(v-1)*v)%mo; 
			}
			else if(a[x]){
				ans=0;
				flag=1;
			}
		}
		for(int i=0;i<=(1<<(2*(n-1)))-1;i++){
			if(flag)break;
			if(allcheck(i)){
				ans++;
			}
		}
		cout<<ans%mo<<endl;
	}
	return 0;
}
/*
Why can't I understand what it said.
那就来点迷惑行为
feropen
//freopen
cin<<
cout>>
itn logn lgno
3倍*icecream!!!
不会要全部情况成立吧
O(n^n)暴力走起！（
暴力都打不出来。。。
又要挂了。。 
诶！v<=2!
状压一手看行不行 
12:17:写不出来。。。挂了
。。。 
rp++;
rp++;
rp++;
rp++;
rp++;
*/
