#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
int read(){
	int tmp=0,f=1;
	char c=getchar();
	while(c< '0')f=c=='-'?-1:1,c=getchar();
	while(c>='0')tmp=(tmp<<3)+(tmp<<1)+(c^'0'),c=getchar();
	return tmp*f;
}
const int M=1e5+1,Mod=1e9+7;
int n,m,v,Aflag=1;
int c[M],d[M],f[M];
void clear(){
	Aflag=1;
	memset(f,0,sizeof f);
}
int qpow(int x,int y){
	if(y==1)return x;
	if(y%2==0)
	return qpow(x,y>>1)*qpow(x,y>>1)%Mod;
	else
	return (qpow(x,y>>1)*qpow(x,y>>1)%Mod)*x%Mod;
}
void work(){
	n=read();m=read();v=read();
	if(n!=m)Aflag=0;
	for(int i=1;i<=m;i++){
		c[i]=read(),d[i]=read();
		if(c[i]!=i)Aflag=0;
	}
	if(m==1){
		printf("%lld\n",qpow(v*v%Mod,n-1));
		return ;
	}
	if(v==2){
		for(int i=1;i<=m;i++){
			if(f[c[i]]){if(f[c[i]]!=d[i]){printf("0\n");return ;}}
			else f[c[i]]=d[i];
		}
		printf("%lld\n",qpow(4,n-1)*3);
		return ;
	}
	
	if(Aflag){
		int ans=(v-1)*v%Mod;
		for(int i=2;i<=n;i++){
			if(i>v)
			ans=ans*(v*v%Mod+1)%Mod;
			else
			ans=(ans*((v-1)*v%Mod+1))%Mod;
		}
		printf("%lld\n",ans+1);
		return ;
	}
	printf("0\n");
	return ;
}
signed main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	int T=read();
	while(T--){
		work();
		clear();
	}
	return 0;
} 
