#include<bits/stdc++.h>
using namespace std;
long long T,n,m,v,mod=1000000007,c[200100],d[200100],cnt;
bool A=1,B=1,D=1;
long long ksm(long long a,long long b){
	long long ans=1;
	while(b){
		if(b&1) ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
void addd(long long c1,long long d1){
	for(long long i=1;i<=cnt;i++){
		if(c1==c[i]){
			if(d[i]!=d1) D=0;
			return ;
		}
	}
	c[++cnt]=c1;d[cnt]=d1;
}
long long mian(){
	cin>>n>>m>>v;
	A=1;B=1;D=1;cnt=0;
	if(m==1){
		long long qaq,oao;
		for(long long i=1;i<=m;i++) cin>>qaq>>oao;
		cout<<ksm((v*v)%mod,n-1)%mod<<endl;
		return 0;
	}
	for(long long i=1;i<=m;i++){
		cin>>c[i]>>d[i];
		addd(c[i],d[i]);
		if(c[i]!=i) A=0;
	}
	if(!D){
		cout<<"0"<<endl;
		return 0;
	}
	if((n==m)&&(A==1)){
		cout<<ksm((v*(v-1)+1)%mod,n-1)%mod<<endl;
		return 0;
	}
	if(cnt==1){
		cout<<ksm((v*v)%mod,n-1)%mod<<endl;
		return 0;
	}
	long long wtp=(n*n)%mod;
	cout<<(long long)(wtp*ksm(cnt+1ll,cnt-1ll))%mod<<endl;
	return 0;
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	cin>>T;
	for(long long i=1;i<=T;i++) mian();
	return 0; 
}
