#include<bits/stdc++.h>
using namespace std;
const int N = 5e2+10;
const int P = 1e9+7;

inline int pow_mod(int x,int k){
   int base = x,res = 1;
   while(k){
      if(k & 1)res = 1LL*res*base%P;
      k >>= 1;
      base = 1LL*base*base%P;
   }
   return res;
}

int fact[N],inv[N];
void init(){
   fact[0] = inv[0] = 1;
   for(int i = 1;i < N; ++i)fact[i] = 1LL*fact[i-1]*i%P;
   inv[N-1] = pow_mod(fact[N-1],P-2);
   for(int i = N-2;i > 0; --i)inv[i] = 1LL*inv[i+1]*(i+1)%P;
}

inline int c(int x,int y){
   return 1LL*fact[x]*inv[x-y]%P*inv[y]%P;
}

int n,m,k;

int gcd(int x,int y){
   if(x < y)swap(x,y);
   return (y == 0)?x:gcd(y,x%y);
}

inline int calc(int x){
   int ret = 0;
   for(int i = 1;i <= x; ++i){
      ret += pow_mod(k,gcd(i,x));
      ret %= P;
   }
   ret = 1LL*ret*pow_mod(x,P-2)%P;
   return ret;
}

stack<int> s1;
vector<int> v1[N];

struct edge{
   int x,y;
}e[N];

int ga[N][N];

vector<int> p[N];
int tot;
int dfn[N],cut[N],low[N];
int ins[N];
int cnt,ct;
void tarjan(int x,int fa,int rt){
   dfn[x] = low[x] = ++cnt;
   ct = 0;
   for(int i = 0;i < (int)v1[x].size(); ++i){
      int y = v1[x][i];
      if(y == fa)continue ;
      if(!dfn[y]){
         s1.push(y); ins[y] = 1;
         tarjan(y,x,rt);
         low[x] = min(low[x],low[y]);
         if(low[y] >= dfn[x]){
            ++ct;
            if(x != rt || ct > 1)cut[x] = 1;
            ++tot;
            int w;
            do {
               w = s1.top(); s1.pop(); ins[w] = 0;
               p[tot].push_back(w);
            }while(w != y);
            p[tot].push_back(x);
         }
      }
      else if(dfn[y] < low[x])low[x] = dfn[y];
   }
}
int vis[N];
int vise[N];
int main(){
   init();
   scanf("%d%d%d",&n,&m,&k);
   for(int i = 1;i <= m; ++i){
      int u,v;
      scanf("%d%d",&u,&v);
      v1[u].push_back(v); v1[v].push_back(u);
      e[i].x = u; e[i].y = v;
      ga[u][v] = i; ga[v][u] = i;
   }
   for(int i = 1;i <= n; ++i){
      if(!dfn[i])tarjan(i,0,i);
   }
   int edgenum;
   int res = 1;
   for(int i = 1;i <= tot; ++i){
      memset(vis,0,sizeof vis);
      for(int j = 0;j < (int)p[i].size(); ++j){
         int y = p[i][j];
         vis[y] = 1;
      }
      edgenum = 0;
      for(int j = 0;j < (int)p[i].size(); ++j){
         int y = p[i][j];
         for(int k = 0;k < (int)v1[y].size(); ++k){
            int w = v1[y][k];
            if(vis[w]){
               ++edgenum;
               vise[ga[y][w]] = 1;
            }
         }
      }
      edgenum /= 2;
      if(edgenum == p[i].size())
         res = 1LL*res*calc(edgenum)%P;
      else if(edgenum == 1 && (int)p[i].size() == 2)
         res = 1LL*res*k%P;
      else 
         res = 1LL*res*c(k-1+edgenum,k-1)%P;
   }
   printf("%d\n",res);
   return 0;
}
