#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
	int q=0;char ch=' ';
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
	return q;
}
const int mod=1e9+7,N=52,M=105;
int n,m,K,ans=1,tot=1,tim,top;
int bin[M],h[N],ne[M<<1],to[M<<1],fac[M<<1],ni[M<<1];
int vis[N],st[M<<1],low[N],dfn[N],orz[M<<1];
void add(int x,int y) {to[++tot]=y,ne[tot]=h[x],h[x]=tot;}
int qm(int x) {return x>=mod?x-mod:x;}
int ksm(int x,int y) {
	int re=1;
	for(;y;y>>=1,x=1LL*x*x%mod) if(y&1) re=1LL*re*x%mod;
	return re;
}
int gcd(int x,int y) {return y?gcd(y,x%y):x;}
int C(int d,int u) {return 1LL*fac[d]*ni[u]%mod*ni[d-u]%mod;}
void tarjan(int x) {
	dfn[x]=low[x]=++tim;
	for(RI i=h[x];i;i=ne[i]) {
		if(orz[i]) continue;
		orz[i]=orz[i^1]=1,st[++top]=i;
		if(!dfn[to[i]]) {
			tarjan(to[i]),low[x]=min(low[x],low[to[i]]);
			if(low[to[i]]>=dfn[x]) {
				int cir=1,js=0,re=0;
				for(RI j=top;st[j+1]!=i;--j,++js)
					if(vis[to[st[j]]]) cir=0;
					else vis[to[st[j]]]=1;
				if(cir) {
					for(RI i=0;i<js;++i) re=qm(re+bin[gcd(i,js)]);
					ans=1LL*ans*re%mod*ksm(js,mod-2)%mod;
				}
				else ans=1LL*ans*C(js+K-1,js)%mod;
				while(st[top+1]!=i) vis[to[st[top]]]=0,--top;
			}
		}
		else low[x]=min(low[x],dfn[to[i]]);
	}
}
int main()
{
	int x,y;
	n=read(),m=read(),K=read();
	bin[0]=1;for(RI i=1;i<=m;++i) bin[i]=1LL*bin[i-1]*K%mod;
	fac[0]=1;for(RI i=1;i<=m+K;++i) fac[i]=1LL*fac[i-1]*i%mod;
	ni[m+K]=ksm(fac[m+K],mod-2);
	for(RI i=m+K-1;i>=0;--i) ni[i]=1LL*ni[i+1]*(i+1)%mod;
	for(RI i=1;i<=m;++i) x=read(),y=read(),add(x,y),add(y,x);
	for(RI i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
	printf("%d\n",ans);
	return 0;
}