#include<bits/stdc++.h>
#define ci const int&
#define C(x,y) (1ll*fac[x]*invf[y]%mod*invf[x-(y)]%mod)
using namespace std;
const int mod=1e9+7;
struct edge{
	int t,nxt;
}e[210];
int n,m,k,fac[210],invf[210],u,v,dfn[55],low[55],cnt,be[55],tot,vis[55],q[55],sz,tn,en[110],in[55],ans=1,t;
vector<int>ps[110];
void add(ci x,ci y){
	e[++cnt].t=y,e[cnt].nxt=be[x],be[x]=cnt;
}
void dfs(ci x,ci f){
	dfn[x]=low[x]=++tot,q[++sz]=x;
	for(int i=be[x];i;i=e[i].nxt)if(!dfn[e[i].t]){
		dfs(e[i].t,x),low[x]=min(low[x],low[e[i].t]);
		if(low[e[i].t]>=dfn[x]){
			++tn,ps[tn].push_back(x);
			while(q[sz]!=e[i].t)ps[tn].push_back(q[sz--]);
			ps[tn].push_back(q[sz--]);
		}
	}else if(e[i].t!=f)low[x]=min(low[x],dfn[e[i].t]);
}
void dfs2(ci x,ci id){
	vis[x]=id;
	for(int i=be[x];i;i=e[i].nxt)if(in[e[i].t]==id){
		++en[id];
		if(vis[e[i].t]!=id)dfs2(e[i].t,id);
	}
}
int gcd(ci x,ci y){
	return y?gcd(y,x%y):x;
}
int POW(int x,int y){
	int ret=1;
	while(y)y&1?ret=1ll*ret*x%mod:0,x=1ll*x*x%mod,y>>=1;
	return ret;
}
int main(){
	scanf("%d%d%d",&n,&m,&k),fac[0]=1;
	for(int i=1;i<=m+k;++i)fac[i]=1ll*fac[i-1]*i%mod;
	invf[m+k]=POW(fac[m+k],mod-2);
	for(int i=m+k-1;i>=0;--i)invf[i]=1ll*invf[i+1]*(i+1)%mod;
	for(int i=1;i<=m;++i)scanf("%d%d",&u,&v),add(u,v),add(v,u);
	for(int i=1;i<=n;++i)if(!dfn[i])sz=0,dfs(i,0);
	for(int i=1;i<=tn;++i){
		for(int j=0;j<ps[i].size();++j)in[ps[i][j]]=i;
		dfs2(ps[i][0],i),en[i]>>=1;
		if(en[i]==1)ans=1ll*ans*k%mod;
		else if(en[i]==ps[i].size()){
			t=0;
			for(int j=0;j<ps[i].size();++j){
				t=(t+POW(k,gcd(j,ps[i].size())))%mod;
			}
			t=1ll*t*POW(ps[i].size(),mod-2)%mod;
			ans=1ll*ans*t%mod;
		}else ans=1ll*ans*C(en[i]+k-1,k-1)%mod;
	}
	printf("%d",ans);
	return 0;
}