#include<bits/stdc++.h>
using namespace std;
using ll = long long;

ll mod = 1e9 + 7;

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll extgcd(ll a, ll b, ll &x, ll &y) { ll d; return b == 0 ? (x = 1, y = 0, a) : (d = extgcd(b, a % b, y, x), y -= a / b * x, d); }
ll modinv(ll a, ll mod = 1e9 + 7) { ll x = 0, y = 0; extgcd(a, mod, x, y); return (x + mod) % mod; }
ll modpow(ll a, ll b, ll mod = 1e9 + 7) { ll r = 1; while(b) { if(b & 1) r = r * a % mod; a = a * a % mod; b >>= 1; } return r; }

// #undef DEBUG
// #define DEBUG
/// {{{ DEBUG --- ///
template <typename T> ostream &operator<<(ostream &o, const vector<T> &v) { if(&o == &cerr) { o << '{'; for(size_t i = 0; i < v.size(); i++) o << v[i] << (i + 1 != v.size() ? ", " : ""); o << "}"; } else { for(size_t i = 0; i < v.size(); i++) o << v[i] << (i + 1 != v.size() ? " " : ""); } return o; }
#ifdef DEBUG
#define dump(...) (cerr<<"["<<__LINE__<< "] "<<#__VA_ARGS__<<" = "<<make_tuple(__VA_ARGS__)<<"\n")
template<int n, class...T> typename enable_if<(n>=sizeof...(T))>::type _ot(ostream &, tuple<T...> const &){}
template<int n, class...T> typename enable_if<(n< sizeof...(T))>::type _ot(ostream & os, tuple<T...> const & t){ os << (n==0?"":", ") << get<n>(t); _ot<n+1>(os, t); }
template<class...T> ostream & operator<<(ostream &o, tuple<T...> const &t){ o << "("; _ot<0>(o, t); o << ")"; return o; }
#else
#define dump(...)
#endif
/// }}}--- ///

vector<int> g[50];
int low[50], ord[50], id = 0;
int used[50];
vector< vector< pair<int, int> > > bc;
vector< pair<int, int> > tmp;

void dfs(int i, int p = -1) {
  low[i] = ord[i] = id++;
  used[i] = 1;
  for(int j : g[i]) if(j != p) {
    pair<int, int> e(min(i, j), max(i, j));
    if(used[j]) {
      if(ord[i] > ord[j]) tmp.emplace_back(e);
      low[i] = min(low[i], ord[j]);
    } else {
      tmp.emplace_back(e);
      dfs(j, i);
      low[i] = min(low[i], low[j]);
      if(low[j] >= ord[i]) {
        bc.push_back({});
        while(1) {
          auto ne = tmp.back();
          bc.back().emplace_back(ne);
          tmp.pop_back();
          if(e == ne) break;
        }
      }
    }
  }
}

ll fact[201], inv[201];
ll C(ll n, ll r) {
  if(n < r) return 0;
  return fact[n] * inv[r] % mod * inv[n - r] % mod;
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  fact[0] = 1;
  for(int i = 1; i <= 200; i++) fact[i] = fact[i - 1] * i % mod;
  inv[200] = modinv(fact[200]);
  for(int i = 199; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % mod;
  int n, m, k; cin >> n >> m >> k;
  for(int i = 0; i < m; i++) {
    int a, b; cin >> a >> b;
    a--; b--;
    g[a].emplace_back(b);
    g[b].emplace_back(a);
  }
  for(int i = 0; i < n; i++) if(!used[i]) dfs(i);
  ll ans = 1;
  for(auto es : bc) {
    set<int> nums; int edge = es.size();
    for(auto e : es) {
      nums.emplace(e.first);
      nums.emplace(e.second);
    }
    int num = nums.size();
    if(num <= 1) {
    } else if(num == 2) {
      ans = ans * k % mod;
    } else {
      if(num == edge) {
        ll res = 0;
        for(int j = 1; j <= edge; j++) res += modpow(k, gcd(j, edge), mod);
        res = res % mod * modinv(edge, mod) % mod;
        ans = res * ans % mod;
      } else {
        ans = C(k + edge - 1, edge) % mod * ans % mod;
      }
    }
  }
  cout << ans << endl;
}



Measured memory_bytes: 256