#include<bits/stdc++.h>
using namespace std;
#define rgsti register int
#define ll long long
const int N=1e9+7;
struct node{
	ll id,val;
};
bool cmp(node e,node f){
	return e.id<f.id;
}
int qs(ll a,ll b){
	ll bas=a,ans=1;
	while(b){
		if(b&1){
			ans*=bas;
			ans%=N;
		}
		bas*=bas;
		bas%=N;
		b/=2;
	}
	return ans;
}
ll t,n,xb1,xb2,tmp1,tmp2,ans,amc,len,m,maxn,cun=0;
node a[100010];
bool f;
map<ll,ll> mp[15];
void dfs(int num,int xb,int ai){
//	cout<<endl;
	if(num>=n){
		if(xb>cun||ai<=0||a[xb].val==ai){
			ans++;
			ans%=N;
		}
		return ;
	}
	
	if(num==a[xb].id){
		if(ai>0&&a[xb].val!=ai) return ;
		for(int i=1;i<=maxn;i++){
			for(int j=1;j<=maxn;j++){
				if(a[xb].val==i){
//					cout<<"1   "<<num<<" "<<xb<<" "<<ai<<endl;
					dfs(num+1,xb+1,j);
				}
				else{
//					cout<<"2   "<<num<<" "<<xb<<" "<<ai<<endl;
					dfs(num+1,xb+1,-1);
				}
			}
		}
	}
	else{
		for(int i=1;i<=maxn;i++){
			for(int j=1;j<=maxn;j++){
				if(ai==i){
				
//					cout<<"3   "<<num<<" "<<xb<<" "<<ai<<endl;
					dfs(num+1,xb,j);
				}
				else{
					
//					cout<<"4   "<<num<<" "<<xb<<" "<<ai<<endl;
					dfs(num+1,xb,-1);
				}
			}
		}
	}
	
//	cout<<endl;
}

int main(){
	
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	
	
	
	cin>>t;
	while(t--){
		ans=0;
		f=cun=0;
		cin>>n>>m>>maxn;
		for(int i=1;i<=100010;i++) a[i].id=a[i].val=0;
		for(int i=1;i<=m;i++){
			cin>>tmp1>>tmp2;
			if(mp[t][tmp1]){
				if(mp[t][tmp1]!=tmp2) f=1;
			}
			else{
				cun++;
				a[cun].id=tmp1;
				a[cun].val=tmp2;
				mp[t][tmp1]=tmp2;
			}
			
			
//			cout<<cun<<" "<<a[cun].id<<" "<<a[cun].val<<endl;
		}
		
		if(f){
			cout<<0<<endl;
			continue;
		}
		
		sort(a+1,a+cun+1,cmp);
		if(n<=12){
		//	cout<<n<<" ";
			dfs(1,1,-1);
			
//			cout<<endl;
//			for(int i=1;i<=cun;i++) cout<<a[i].id<<" "<<a[i].val<<endl;
			
		}
		else if(m==1){
			maxn=(maxn*maxn)%N;
			ans=qs(maxn,n-1);
		}
		
	//	cout<<n<<"     ";
		
		cout<<ans<<endl;
	//	for(int i=1;i<=20000;i++) cout<<"******************"<<endl;
	}
	
	
	
	
	
	return 0;
} 
