#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <memory.h>

using namespace std;
typedef long long LL;
const int maxn = 205;
const int mod = 1e9+7;
const int N = 200;

int ehead[maxn],ecnt=1;
struct edge {
	int u,v,next;
}edg[maxn<<1];
void add(int u,int v) {
	edg[++ecnt]=(edge){u,v,ehead[u]};
	ehead[u]=ecnt;
	edg[++ecnt]=(edge){v,u,ehead[v]};
	ehead[v]=ecnt;
}
int n,m,K,pw[maxn],fac[maxn],inc[maxn];
LL fpm(LL p,LL k) {
	LL res=1ll;
	while (k) {
		if (k&1) (res*=p)%=mod;
		(p*=p)%=mod;k>>=1;
	}
	return res;
}
int gcd(int n,int m) {
	return m?gcd(m,n%m):n;
}
int polya(int n)
{
	int ans=0;
	for (int i=1;i<=n;i++)
		ans=(ans+pw[gcd(n,i)])%mod;
	return ans*fpm(n,mod-2)%mod;
}
LL comb(int n,int m) {
	return (LL)fac[n]*inc[m]%mod*(LL)inc[n-m]%mod;
}
int dfn[maxn],idx,low[maxn],stk[maxn],top;
bool vis[maxn];LL ans=1ll;
void solve(int pos)
{
	memset(vis,0,sizeof vis);
	int cnte=0,cntn=0;
	while (top!=pos) {
		++cnte;int i=stk[top--];
		vis[edg[i].u]=vis[edg[i].v]=true;
	}
	for (int i=1;i<=n;i++) cntn+=vis[i];
	if (!cnte) return ;
	if (cnte<=1) ans=(LL)ans*K%mod;
	else if (cnte!=cntn) ans=(LL)ans*comb(cnte+K-1,K-1)%mod;
	else ans=(LL)ans*polya(cntn)%mod;
}
void tarjan(int u,int faj)
{
	low[u]=dfn[u]=++idx;
	for (int v,j=ehead[u];j;j=edg[j].next)
	if (j/2!=faj) {
		if (!dfn[v=edg[j].v]) {
			int pos=top;stk[++top]=j;
			tarjan(v,j>>1);
			if (low[v]>=dfn[u]) solve(pos);
			low[u]=min(low[u],low[v]);
		}
		else if (dfn[v]<dfn[u]) {
			stk[++top]=j;
			low[u]=min(low[u],dfn[v]);
		}
	}
	if (!faj) solve(0);
}
int main()
{
	#ifdef Amberframe
		freopen("arc062f.in","r",stdin);
		freopen("arc062f.out","w",stdout);
	#endif
	scanf("%d %d %d",&n,&m,&K);fac[0]=inc[0]=pw[0]=1;
	for (int i=1;i<=N;i++) pw[i]=(LL)pw[i-1]*K%mod;
	for (int i=1;i<=N;i++) fac[i]=(LL)fac[i-1]*i%mod;
	inc[N]=fpm(fac[N],mod-2);
	for (int i=N;i>=2;i--) inc[i-1]=(LL)inc[i]*i%mod;
	for (int u,v,i=1;i<=m;i++)
		scanf("%d %d",&u,&v),add(u,v);
	for (int i=1;i<=n;i++)
		if (!dfn[i]) tarjan(i,0);
	printf("%d",ans);
	return 0;
}