#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=1e9+7;
ll T,n,m,v,t,f,x,mm,ans,a[100005],b[100005],c[100005],d[100005],e[100005],bz[100005];
void dfs(ll d){
	if(t) return;
	if(d>n){
		for(ll i=1;i<n;i++) if(e[i]==a[i]&&e[i+1]!=b[i]) return;
		t=1;
		return;
	}
	for(ll i=1;i<=v;i++){
		if(bz[d]&&bz[d]!=i) continue;
		e[d]=i;
		dfs(d+1);
	}
}
void ss1(ll d){
	if(d==n){
		t=0;
		dfs(1);
		if(t) ans=(ans+1)%mod;
		return;
	}
	for(ll i=1;i<=v;i++){
		b[d]=i;
		ss1(d+1);
	}
}
void ss(ll d){
	if(d==n){
		ss1(1);
		return;
	}
	for(ll i=1;i<=v;i++){
		a[d]=i;
		ss(d+1);
	}
}
void pw(ll A,ll B){
	ll g=1,h=1,y=A;
	x=A;
	while(g*2<=B){
		g*=2;
		x=(x*x)%mod;
	}
	while(h*2+g<=B){
		h*=2;
		y=(y*y)%mod;
	}
	x=(x*y)%mod;
	for(int i=g+h;i<B;i++) x=(x*A)%mod;
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%lld",&T);
	while(T--){
		scanf("%lld%lld%lld",&n,&m,&v);
		ans=f=0,mm=m;
		memset(bz,0,sizeof(bz));
		for(ll i=1;i<=m;i++){
			scanf("%lld%lld",&c[i],&d[i]);
			if(c[i]<1e5){
				if(bz[c[i]]&&bz[c[i]]!=d[i]) f=1;
				if(bz[c[i]]) mm--;
				bz[c[i]]=d[i];
			}
		}
		if(f){
			printf("0\n");
			continue;
		}
		if(n<13){
			if(max(c[1],c[2])-min(c[1],c[2])==1) ss(1);
			else x=pow(v,n-1),ans=(x*x)%mod;
			printf("%lld\n",ans);
			continue;
		}
		if(m==1){
			pw(v,n-1);
			ans=(x*x)%mod;
			printf("%lld\n",ans);
		}
	}
	return 0;
}
