#include <bits/stdc++.h>

using std::min;

typedef long long LL;

const int N=210,Mod=1e9+7;

struct Edge{ int to,next; }way[N<<1];

int n,m,k,num[N],tot,cntnode[N],cntedge[N],cnt,inv[N],C[N][N];

int gcd(int a,int b) { return (!b)?a:gcd(b,a%b); }

void Build(int a,int b) { way[++tot]=(Edge){b,num[a]}; num[a]=tot; }

void Init() {
	scanf("%d%d%d",&n,&m,&k);
	int a,b; tot=1;
	for (int i=1;i<=m;++i) {
		scanf("%d%d",&a,&b);
		Build(a,b);
		Build(b,a);
	}
}

int dfn[N],cntdfn,low[N],que[N],top;
bool divv[N],vis[N],app[N];

void Dfs(int x,int fa) {
	dfn[x]=low[x]=++cntdfn;
	int son=0;
	for (int i=num[x];i;i=way[i].next) {
		int v=way[i].to;
		if (v==fa) continue;
		if (dfn[v]) {
			if (dfn[v]<dfn[x]){
				low[x]=min(low[x],dfn[v]);
				que[++top]=i;
			}
		}else {
			que[++top]=i;
			Dfs(v,x); ++son;
			low[x]=min(low[x],low[v]);
			if (v==19)
				v++,v--;
			if ((fa || son>=2) && low[v]>=dfn[x]){
				++cnt; int d=top;
				while (que[top]!=i) {
					cntedge[cnt]++;
					if (!app[way[que[top]].to]) app[way[que[top]].to]=1,cntnode[cnt]++;
					if (!app[way[que[top]^1].to]) app[way[que[top]^1].to]=1,cntnode[cnt]++;
					top--;
				}
				if (!app[way[que[top]].to]) app[way[que[top]].to]=1,cntnode[cnt]++;	
				if (!app[way[que[top]^1].to]) app[way[que[top]^1].to]=1,cntnode[cnt]++;	
				cntedge[cnt]++; top--;
				while (que[d]!=i) {
					app[way[que[d]].to]=0;
					app[way[que[d]^1].to]=0;
					d--;
				}
				app[way[que[d]].to]=0; app[way[que[d]^1].to]=0; d--;
			}
		}
	}
	if (!fa && top) {
		++cnt; int d=top;
		while (top) {
			cntedge[cnt]++;
			if (!app[way[que[top]].to]) app[way[que[top]].to]=1,cntnode[cnt]++;
			if (!app[way[que[top]^1].to]) app[way[que[top]^1].to]=1,cntnode[cnt]++;
			top--;
		}
		while (d) {
			app[way[que[d]].to]=0;
			app[way[que[d]^1].to]=0;
			d--;
		}	
	}
}

void Tarjan() {
	cnt=0; cntdfn=0;
	for (int i=1;i<=n;++i) if (!dfn[i]) Dfs(i,0);
}

int power(int x,int t) {
	int ret=1;
	while (t) {
		if (t&1) ret=1ll*ret*x%Mod;
		x=1ll*x*x%Mod;
		t>>=1;
	}
	return ret;
}

void Prepare() {
	inv[1]=1; for (int i=2;i<=m;++i) inv[i]=1ll*(Mod-Mod/i)*inv[Mod%i]%Mod;
	C[0][0]=1; 
	for (int i=1;i<=m+k;++i) {
		C[i][0]=1;
		for (int j=1;j<=i;++j)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%Mod;
	}
}

void Solve() {
	Tarjan();
	Prepare();
	LL ans=1;
	for (int i=1;i<=cnt;++i) {
		if (cntnode[i]==cntedge[i]) {
			int sum=0;
			for (int j=1;j<=cntedge[i];++j) 
				sum=(sum+power(k,gcd(j,cntedge[i])))%Mod;
			sum=1ll*sum*inv[cntedge[i]]%Mod;
			ans=1ll*ans*sum%Mod;
		}else ans=1ll*ans*C[cntedge[i]+k-1][k-1]%Mod;
	}
	printf("%lld\n",ans);
}

int main() {
	Init();
	Solve();
	return 0;
}