#include <stdio.h>
#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;
const int Q=1<<12,P=1<<16;
int ops;
int inc=1,Time;
int las[Q],e[P],nn[P];
int dfn[Q],low[Q];
int st[Q],tp=0;
int bel[Q];
int scc=0;
const int MOD=1e9+7;
int add(int a,int b)
{a+=b;return a>=MOD?a-MOD:a;}
int mul(int a,int b)
{return 1LL*a*b%MOD;}
int ksm(int a,int b)
{
	int ans=1;
	for(;b;b>>=1,a=mul(a,a))
		if(b&1)ans=mul(ans,a);
	return ans;
}
int C(int n,int m)
{
	int t1=1,t2=1;
	for(int i=0;i<m;i++){
		t1=mul(t1,n-i);
		t2=mul(t2,m-i);
	}
	return mul(t1,ksm(t2,MOD-2));
}
int gcd(int a,int b)
{return b?gcd(b,a%b):a;}
int k;
int Po(int x)
{
	int tmp=0;
	for(int i=1;i<=x;i++)tmp=add(tmp,ksm(k,gcd(i,x)));
	return mul(tmp,ksm(x,MOD-2));
}
int als=1;
void DEAL(int last,int x)
{
	++scc;
	int now;
	int lim=tp;
	do{
		now=st[tp--];
		bel[now]=scc;
	}while(now!=x);
	bel[last]=scc;
	int pn=lim-tp+1,pm=0;
	for(int i=tp;i<=lim;i++){
		int x=st[i];
		if(i==tp)x=last;
		for(int t=las[x];t;t=nn[t]){
			int y=e[t];
			if(bel[y]==scc)++pm;
		}
	}
	pm>>=1;
	if(pn==pm)als=mul(als,Po(pn));
	else if(pm<pn)als=mul(als,k);
	else als=mul(als,C(pm+k-1,k-1));
}
void dfs(int x)
{
	dfn[x]=low[x]=++Time;
	st[++tp]=x;
	for(int t=las[x];t;t=nn[t]){
		int y=e[t];
		if(!dfn[y]){
			dfs(y);
			if(dfn[x]<=low[y])DEAL(x,y);
			low[x]=min(low[x],low[y]);
		}
		else low[x]=min(low[x],dfn[y]);
	}
}
void ins(int x,int y)
{
	e[++inc]=y;
	nn[inc]=las[x];
	las[x]=inc;
}
int n,m;
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1,x,y;i<=m;i++)
		scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
	for(int i=1;i<=n;i++)
		if(!dfn[i])dfs(i);
	printf("%d",als);
	return 0;
}