#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
long long t,n,m,v,c[100001],d[100001],vv[100001],x[100001],aa[100001];
long long ans;
long long dfs(long long a,long long b,long long c){
	if(c==a){
		return b%mod;
	}if(c*2>a){
		return b*dfs(a-c,v*v%mod,1)%mod;
	}b=b*b%mod;
	c+=c;
	return dfs(a,b,c)%mod;
}long long dfs2(long long a,long long b,long long c){
	if(c==a){
		return b%mod;
	}if(c*2>a){
		return b*dfs2(a-c,(v*(v-1)%mod+1)%mod,1)%mod;
	}b=b*b%mod;
	c+=c;
	return dfs2(a,b,c)%mod;
}void dfs3(int a){
	if(a==n){
		int lst=0;
		for(int j=1;j<=n;j++){
			if(lst){
				if(vv[j]&&vv[j]!=lst)return ;
				if(!vv[j])lst=0;
			}if(vv[j]==x[j])lst=aa[j];
		}ans++;
		return ;
	}for(int i=1;i<=v;i++){
		x[a]=i;
		for(int j=1;j<=v;j++){
			aa[a]=j;
			dfs3(a+1);
		}
	}
}int 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--){
		for(int i=1;i<=n;i++){
			vv[i]=0;
		}bool bb=1;
		ans=0;
		cin>>n>>m>>v;
		for(int i=1;i<=m;i++){
			cin>>c[i]>>d[i];
			if(vv[c[i]]&&vv[c[i]]!=d[i]){
				bb=0;
			}vv[c[i]]=d[i];
		}if(!bb){
			cout<<"0\n";
			continue;
		}if(m==1){//6-9
			cout<<dfs(n-1,v*v%mod,1)<<"\n";
		}else if(m==n){//10-12
			cout<<dfs2(n-1,(v*(v-1)%mod+1)%mod,1)<<"\n";
		}else {
			dfs3(1);
			cout<<ans<<"\n";
		}
	}
	return 0;
}
/*
256
0
4096
129600
4194304
503279958
748525720
892897109
174281099
418965370


*/
