#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,Mod=1e9+7;
int T,n,m,v,ans,la;
int c[N],d[N],fa[N],fb[N],x[N];
int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=res*a%Mod;
		b>>=1;
		a=a*a%Mod;
	}
	return res;
}
bool check(){
	for(int i=1; i<=n; i++) x[i]=0;
	for(int i=1; i<=m; i++) x[c[i]]=d[i];
	for(int i=1; i<n; i++){
		if(fa[i]==x[i]){
			if(x[i+1]==0) x[i+1]=fb[i];
			if(x[i+1]!=fb[i]) return 0;
		}
	}
	return 1;
}
void dfs(int k){
	if(k==n){
		if(check()) ans++;
		return;
	}
	for(int i=1; i<=v; i++){
		for(int j=1; j<=v; j++){
			fa[k]=i,fb[k]=j;
			dfs(k+1);
		}
	}
}
bool checkB(){
	for(int i=1; i<=m; i++){
		if(d[i]!=1) return 0;
	}
	return 1;
}
int mo(int a,int b){
	return (a%b+b)%b;
}
void solve(){
	scanf("%lld%lld%lld",&n,&m,&v);
	for(int i=1; i<=m; i++) scanf("%lld%lld",&c[i],&d[i]);
	if(n<=12){
		for(int i=1; i<=n; i++) fa[i]=0;
		for(int i=1; i<=n; i++) fb[i]=0;
		for(int i=1; i<=n; i++) x[i]=0;
		for(int i=1; i<=m; i++){
			if(x[c[i]]){
				if(x[c[i]]!=d[i]){
					puts("0");
					return;
				}
			} 
			else x[c[i]]=d[i];
		}
		ans=0;
		dfs(1); 
		printf("%lld\n",ans);
		return;
	} 
	if(m==1){
		printf("%lld\n",qpow(v,2*n-2));
		return;
	}
	if(n==m){
		printf("%lld\n",qpow((v*(v-1)+1)%Mod,n-1));
		return;
	}
	puts("0");
}
signed main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%lld",&T);
	while(T--) solve();
	return 0;
}

