#include<bits/stdc++.h>
using namespace std;
const int M=4e5+5,P=1e9+7;
int n,m,K;
int head[M],asdf;
struct edge{
	int to,nxt,id;
}G[M<<1];
void add_edge(int a,int b,int c){
	G[++asdf].to=b;
	G[asdf].nxt=head[a];
	G[asdf].id=c;
	head[a]=asdf;
}
int fast(int a,int b){
	int res=1;
	while(b>0){
		if(b&1)res=1ll*res*a%P;
		a=1ll*a*a%P;
		b>>=1;
	}
	return res;
}
bool mark[M],vis[M];
int dfn[M],low[M],cyc[M],tot;
void tarjan(int x,int f){
	dfn[x]=low[x]=++tot;
	for(int i=head[x];i;i=G[i].nxt){
		int y=G[i].to;
		if(!dfn[y]){
			tarjan(y,G[i].id);
			low[x]=min(low[x],low[y]);
			if(low[y]>dfn[x]){
				mark[G[i].id]=1;
			}
		}else if(G[i].id!=f){
			low[x]=min(low[x],dfn[y]);
		}
	}
}
int cnt;
void dfs(int x,int f){
	if(vis[x])return;
	vis[x]=1;
	cnt++;
	for(int i=head[x];i;i=G[i].nxt){
		if(mark[G[i].id])continue;
		int y=G[i].to;
		dfs(y,x);
	}
}
int main(){
	int cas;
	scanf("%d",&cas);
	while(cas--){
		scanf("%d %d %d",&n,&m,&K);
		asdf=0;
		tot=0;
		int nik=fast(K,P-2);
		int tmp=1;
		for(int i=1;i<=n;i++){
			head[i]=0;
			dfn[i]=low[i]=0;
			vis[i]=0;
			if(i==1){
				cyc[1]=K;
			}else if(i==2){
				cyc[2]=1ll*K*(K-1)%P;
			}else {
				cyc[i]=(1ll*tmp*K-cyc[i-1])%P;
			}
			tmp=1ll*tmp*(K-1)%P;
			//if(i<=5)printf("cyc[%d]=%d\n",i,cyc[i]);
		}
		for(int i=1;i<=m;i++){
			mark[i]=0;
			int a,b;
			scanf("%d %d",&a,&b);
			add_edge(a,b,i);
			add_edge(b,a,i);
		}
		tarjan(1,0);
		int ans=1;
		int tp=0;
		for(int i=1;i<=n;i++){
			if(!vis[i]){
				cnt=0;
				dfs(i,0);
				if(cnt>1){
					ans=1ll*ans*cyc[cnt]%P;
					//printf("cyc[%d]=%d\n",cnt,cyc[cnt]);
					if(!tp)ans=ans;
					else ans=1ll*ans*(K-1)%P*nik%P;
					tp++;
				}else {
					if(!tp)ans=1ll*ans*K%P;
					else ans=1ll*ans*(K-1)%P;
					tp++;
				}
			}
		}
		ans=(ans%P+P)%P;
		printf("%d\n",ans);
	}
	return 0;
}