#include "bits/stdc++.h"\
#define int long long
using namespace std;
const int N=1e5+10;
const int md=1e9+7;
int T,n,m,v,x[N],f1,cc[N];
int re(){
	int x=0,f=1;char s=getchar();
	while(!isdigit(s)){
		if(s=='-')	f=-1;
		s=getchar();
	}
	while(isdigit(s))	x=x*10+s-'0',s=getchar();
	return x*f;
} 
int qui(int x,int p){
	int res=1;
	while(p){
		if(p%2) res=(res*x)%md;
		x=(x*x)%md;
		p/=2;
	}
	return res;
}
void init(){
	f1=0;
}
signed main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	T=re();
	while(T--){
		init();
		n=re(),m=re(),v=re();
		if(n!=m)	f1=1;
		for(int i=1;i<=m;i++){
			int c=re(),d=re();
			cc[i]=c;
			if(c!=i)	f1=1;
		}
		if(f1==0){
			cout<<(qui((v*(v-1)%md+1)%md,n-1)+md)%md<<'\n';
		}
		else	cout<<0<<'\n';
	}
	return 0;
}
