#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int ans,n,t,m,v,c[100005],b[100005],a[100005],d[100005],xz[100005];
int qpow(int a,int b){
	int ans=1,p=a;
	while(b){
		if(b&1)ans=ans*p%mod;
		p=p*p%mod;
		b>>=1;
	}
	return ans;
}
void dfs(int k){
	if(k==2*n-1){
		bool f=1;
		for(int i=1;i<=n;i++)b[i]=a[i];
		for(int i=1;i<n;i++){
			int st=2*i-1;
			if(b[i]==xz[st]&&b[i+1]!=-1&&b[i+1]!=xz[st+1]){
				f=0;
				break;
			}
			if(b[i]==xz[st]){
				b[i+1]=xz[st+1];
			}
		}
		ans+=f;
		return;
	}
	for(int i=1;i<=v;i++){
		xz[k]=i;
		dfs(k+1);
	}
}
signed main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	while(t--){
		cin>>n>>m>>v;
		bool f=1;
		for(int i=1;i<=m;i++){
			cin>>c[i]>>d[i];
		}
		if(m==1){
			cout<<qpow(v,2*n-2)<<'\n';
			continue;
		}
		ans=0;
		if(m<=12&&n<=12){
			for(int i=1;i<=n;i++)a[i]=-1;
			for(int i=1;i<=m;i++){
				if(a[c[i]]==-1)a[c[i]]=d[i];
				else{
					if(a[c[i]]!=d[i]){
						f=0;
						break;
					}
				}
			}
			if(f==0){
				cout<<0<<'\n';
				continue;
			}
			dfs(1);
			cout<<ans<<'\n';
			continue;
		}
		for(int i=1;i<=n;i++)a[i]=-1;
		for(int i=1;i<=m;i++){
			a[c[i]]=d[i];
		}
		ans=1;
		for(int i=1;i<n;i++){
			int mul=v*v-v+1;
			mul%=mod;
			ans=ans*mul%mod;
		}
		cout<<ans<<'\n';
	}
}

