#include<algorithm>
#include<iostream>
#include<map>
using namespace std;
const int N=1000005,mod=1e9+7;
int T,n,m,v,c,d,ans,a[N],A[N],B[N],K[N];
map<int,int> mp;
int ksm(int x,int y){
	long long ans=1,pow=x;
	while(y){
		if(y&1)ans=ans*pow%mod;
		pow=pow*pow%mod;
		y>>=1;
	}
	return ans;
}
void dfs(int x){
	if(x>=n){
		for(int i=1;i<=n;i++)K[i]=a[i];
		for(int i=1;i<n;i++){
			if(K[i]){
				if(A[i]==K[i]){
					if(K[i+1]&&K[i+1]!=B[i])return ;
					K[i+1]=B[i];
				}
			}
		}
		ans++;
		return ;
	}
	for(int i=1;i<=v;i++){
		for(int j=1;j<=v;j++){
			A[x]=i;B[x]=j;
			dfs(x+1);
		}
	}
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	cin>>T;
	while(T--){
		cin>>n>>m>>v;
		bool flag=false;
		mp.clear();
		for(int i=1;i<=m;i++){
			cin>>c>>d;
			if(!mp[c])mp[c]=d;
			else if(mp[c]!=d)flag=true;
		}
		if(flag)cout<<"0\n";
		else if(m==1)cout<<ksm(v*1ll*v%mod,n-1)<<"\n";
		else{
			for(map<int,int>::iterator it=mp.begin();it!=mp.end();it++)a[(*it).first]=a[(*it).second];
			ans=0;
			dfs(1);
			cout<<ans<<"\n";
		}
	}
	return 0;
}
