#include<iostream>
#include<cstdio>
#include<cstring>
#define mod 1000000007
using namespace std;
int h[101000],nxt[201000],K=0,to[201000],from[201000];
int dfs[101000],low[101000],dfn=0,st[101000],top=0,tot=0,used[101000];
long long fac[101000],inv[101000];
long long ans=1;int n,m,k;
long long C(int a,int b){return fac[a]*inv[b]%mod*inv[a-b]%mod;}
void ins(int u,int v){nxt[++K]=h[u];h[u]=K;to[K]=v;from[K]=u;}
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
long long qpow(long long x,int p)
{
	long long ans=1;
	while(p){if(p&1)ans=ans*x%mod;x=x*x%mod;p>>=1;}
	return ans;
}
void tarjan(int x,int f)
{
	dfs[x]=low[x]=++dfn;
	for(int i=h[x];i;i=nxt[i])
	{
		if(to[i]==f)continue;
		if(!dfs[to[i]])
		{
			st[++top]=i;tarjan(to[i],x);
			low[x]=min(low[x],low[to[i]]);
			if(low[to[i]]>=dfs[x])
			{
				tot++;int N=0,M=0;
				while(1)
				{
					if(used[from[st[top]]]!=tot)used[from[st[top]]]=tot,N++;
					if(used[to[st[top]]]!=tot)used[to[st[top]]]=tot,N++;
					M++;
					if(st[top--]==i)break;
				}
				if(N==2)ans=ans*k%mod;
				else if(N==M)
				{
					long long res=0;
					for(int j=1;j<=M;j++)res=(res+qpow(k,gcd(j,M)))%mod;
					res=res*qpow(M,mod-2)%mod;
					ans=ans*res%mod;
				}
				else
				{
					ans=ans*C(M+k-1,k-1)%mod;
				}
			}
		}
		else if(dfs[to[i]]<dfs[x])st[++top]=i,low[x]=min(low[x],dfs[to[i]]);
	}
}
int main()
{
	fac[0]=inv[0]=inv[1]=1;
	for(int i=1;i<=200;i++)fac[i]=fac[i-1]*i%mod;
	for(int i=2;i<=200;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	for(int i=1;i<=200;i++)inv[i]=inv[i-1]*inv[i]%mod;
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=m;i++)
	{
		int a,b;scanf("%d%d",&a,&b);ins(a,b);ins(b,a);
	}
	for(int i=1;i<=n;i++)if(!used[i])tarjan(i,0);
	printf("%lld\n",ans);return 0; 
}