#include<cstdio>
const int mod=1000000007;
int N,M,K;
struct edge{int to;edge*next;}E[210],*ne=E,*fir[110];
void link(int u,int v){*ne=(edge){v,fir[u]};fir[u]=ne++;}
long long inv(int a,int p=mod){return a==1?1:(1+p*(a-inv(p%a,a)))/a%p;}
int dfn[110],low[110],now,stk[110],top,bcc[110],bcnt,vs[110],es[110];
void dfs(int i){
	dfn[i]=low[i]=++now;
	stk[top++]=i;
	for(edge*e=fir[i];e;e=e->next){
		if(!dfn[e->to]){
			dfs(e->to);
			if(low[e->to]>=dfn[i]){
				vs[++bcnt]=1;
				do bcc[stk[--top]]=bcnt,vs[bcnt]++;
				while(stk[top]!=e->to);
			}
			if(low[e->to]<low[i])low[i]=low[e->to];
		}
		else if(dfn[e->to]<low[i])low[i]=dfn[e->to];
	}
}
int pr[110],phi[110],pc,pw[110];
bool com[110];
int fac[210],ifac[210];
int main(){
	scanf("%d%d%d",&N,&M,&K);
	for(int i=0,a,b;i<M;i++)scanf("%d%d",&a,&b),link(a,b),link(b,a);
	phi[1]=1;
	for(int i=2;i<=M;i++){
		if(!com[i])pr[pc++]=i,phi[i]=i-1;
		for(int j=0;j<pc&&i*pr[j]<=M;j++){
			com[i*pr[j]]=1;
			if(i%pr[j]==0){
				phi[i*pr[j]]=phi[i]*pr[j];
				break;
			}
			phi[i*pr[j]]=phi[i]*(pr[j]-1);
		}
	}
	for(int i=*pw=1;i<=M;i++)pw[i]=1ll*pw[i-1]*K%mod;
	for(int i=*fac=1;i<=M+K;i++)fac[i]=1ll*fac[i-1]*i%mod;
	ifac[M+K]=inv(fac[M+K]);
	for(int i=M+K;i;i--)ifac[i-1]=1ll*ifac[i]*i%mod;
	int ans=1;
	for(int i=1;i<=N;i++)if(!dfn[i])dfs(i);
	for(int i=1;i<=N;i++)
		for(edge*e=fir[i];e;e=e->next)
			es[dfn[e->to]>dfn[i]?bcc[e->to]:bcc[i]]++;
	for(int i=1;i<=bcnt;i++){
		int m=es[i]/2;
		if(m==vs[i]){
			int s=0;
			for(int i=1;i<=m;i++)if(m%i==0)s=(s+1ll*pw[i]*phi[m/i])%mod;
			ans=(1ll*ans*s%mod*fac[m-1]%mod*ifac[m])%mod;
		}
		else ans=(1ll*ans*fac[m+K-1]%mod*ifac[m]%mod*ifac[K-1])%mod;
	}
	printf("%d\n",ans);
}