#include<bits/stdc++.h>
#define inf 2147483647
#define ll long long
#define N 1010
#define MOD (ll)(1000000007)
using namespace std;
ll n,m,v,T;
ll c[N],d[N];
ll x[N],a[N],b[N];
ll vis[N]={0};
ll ans=0;
bool check(){
	for(int i=1;i<n;++i)
		if(a[i]==x[i])
			if(x[i+1]!=b[i])
				return 0;
	return 1;
}int dfsx(int t){
	if(t>n){
		return check();
	}if(vis[t]){
		x[t]=vis[t];
		return dfsx(t+1);
	}else{
		for(int i=1;i<=v;++i){
			x[t]=i;
			if(dfsx(t+1))
				return 1;
		}
	}return 0;
}
void dfsab(int k1,int k2){
	if(k2>=n){
		if(dfsx(1))
			++ans;
		return ;
	}
	if(k1<n){
		for(int i=1;i<=v;++i){
			a[k1]=i;
			dfsab(k1+1,k2);
		}
	}else{
		for(int i=1;i<=v;++i){
			b[k2]=i;
			dfsab(k1,k2+1);
		}
	}
	
	
}ll fpow(ll x,ll y){
	__int128 s=1,tmp=x;
	while(y){
		if(y&1) s=(s*tmp)%MOD;
		tmp=(tmp*tmp)%MOD;
		y>>=1;
	}return (ll)(s%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);
		if(m==1){
			ll tmp1,tmp2;
			scanf("%lld%lld",&tmp1,&tmp2);
			printf("%lld\n",fpow(v,((n-1)<<1)));
			continue;
		}if(n<=100){
			int flag=0;
			for(int i=1;i<=m;++i){
				scanf("%lld%lld",&c[i],&d[i]);
				if(vis[c[i]]&&vis[c[i]]!=d[i]) flag=1;
				vis[c[i]]=d[i];
			}if(flag) ans=0;
			else dfsab(1,1);
			cout<<ans<<'\n';
			continue;
		}
	}


//	fclose(stdin);
//	fclose(stdout);
	return 0;
} 
