#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
#define MOD 1000000007
using namespace std;
const int MAXN = 205;
typedef long long ll;
struct Edge{
  int to,next;
}e[MAXN<<1];
int head[MAXN],n,cnt=1,m,c,cut_cnt;
inline void insert(int u,int v)
{
  e[++cnt].to=v,e[cnt].next=head[u],head[u]=cnt;
  e[++cnt].to=u,e[cnt].next=head[v],head[v]=cnt;
}
set<int>block[MAXN];
int dfn[MAXN],low[MAXN],block_cnt,dfs_clock,stk[MAXN],top,cut[MAXN];
void tarjan(int x,int fa,int from)
{
  low[x]=dfn[x]=++dfs_clock,stk[++top]=x;
  for(int i=head[x];i;i=e[i].next){
    int v=e[i].to;
    if(v==fa)continue;
    if(!dfn[v]){
      tarjan(v,x,i);
      if(low[v]>=dfn[x]){
	int u;
	cut[i]=cut[i^1]=true;
	++cut_cnt;
		
	++block_cnt;
	while(true){
	  u=stk[top--];
	  block[block_cnt].insert(u);
	  if(u==v)break;
	}
	block[block_cnt].insert(x);
      }
      low[x]=min(low[x],low[v]);
    }
    else low[x]=min(low[x],dfn[v]);
  }	
}
inline ll gcd(ll a,ll b)
{
  return b==0?a:gcd(b,a%b);
}
inline ll ksm(ll x,ll k)
{
  ll ret=1;
  while(k){
    if(k&1)ret=ret*x%MOD;
    x=x*x%MOD;
    k>>=1;
  }
  return ret;
}
ll fac[MAXN*10],inv[MAXN*10];
inline ll C(int n,int m)
{
  return fac[m]*inv[n]%MOD*inv[m-n]%MOD;
}
inline void init()
{
  fac[0]=1;
  for(int i=1;i<=2000;++i)fac[i]=fac[i-1]*i%MOD;
  inv[2000]=ksm(fac[2000],MOD-2);
  for(int i=1999;i>=0;--i)inv[i]=inv[i+1]*(i+1)%MOD;
}
int main()
{
  init();
  scanf("%d%d%d",&n,&m,&c);
  for(int i=1;i<=m;++i){
    int u,v;
    scanf("%d%d",&u,&v);
    insert(u,v);
  }
  for(int i=1;i<=n;++i){
    if(!dfn[i])tarjan(i,0,0);
  }
  ll ans=1;
  for(int i=1;i<=block_cnt;++i){
    int n_cnt=block[i].size(),m_cnt=0;
    for(set<int>::iterator j=block[i].begin();j!=block[i].end();++j){
      for(int k=head[*j];k;k=e[k].next){
	if(block[i].count(e[k].to))++m_cnt;
      }
    }
    m_cnt>>=1;
    if(m_cnt>n_cnt){
      ans=ans*C(c-1,m_cnt+c-1)%MOD;
    }else if(m_cnt==n_cnt){
      ll t=0;
      for(int i=0;i<n_cnt;++i){
	t=(t+ksm(c,gcd(i,n_cnt)))%MOD;
      }
      ans=ans*t%MOD*ksm(n_cnt,MOD-2)%MOD;
    }else{
      ans=ans*c%MOD;
    }
  }
  cout<<ans%MOD<<endl;
  return 0;
}
