#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

const ll mod = 1000000007;
typedef vector<vector<int>> UnWeightedGraph;

template< typename G >
struct LowLink {
  const G &g;
  vector< int > used, ord, low;
  vector< int > articulation;
  vector< pair< int, int > > bridge;
 
  LowLink(const G &g) : g(g) {}
 
  int dfs(int idx, int k, int par) {
    used[idx] = true;
    ord[idx] = k++;
    low[idx] = ord[idx];
    bool is_articulation = false;
    int cnt = 0;
    for(auto &to : g[idx]) {
      if(!used[to]) {
        ++cnt;
        k = dfs(to, k, idx);
        low[idx] = min(low[idx], low[to]);
        is_articulation |= ~par && low[to] >= ord[idx];
        if(ord[idx] < low[to]) bridge.emplace_back(minmax(idx, (int) to));
      } else if(to != par) {
        low[idx] = min(low[idx], ord[to]);
      }
    }
    is_articulation |= par == -1 && cnt > 1;
    if(is_articulation) articulation.push_back(idx);
    return k;
  }
 
  virtual void build() {
    used.assign(g.size(), 0);
    ord.assign(g.size(), 0);
    low.assign(g.size(), 0);
    int k = 0;
    for(int i = 0; i < g.size(); i++) {
      if(!used[i]) k = dfs(i, k, -1);
    }
  }
};

template< typename G >
struct BiConnectedComponents : LowLink< G > {
  using LL = LowLink< G >;
 
  vector< int > used;
  vector< vector< pair< int, int > > > bc;
  vector< pair< int, int > > tmp;
 
  BiConnectedComponents(const G &g) : LL(g) {}
 
  void dfs(int idx, int par) {
    used[idx] = true;
    for(auto &to : this->g[idx]) {
      if(to == par) continue;
      if(!used[to] || this->ord[to] < this->ord[idx]) {
        tmp.emplace_back(minmax(idx, to));
      }
      if(!used[to]) {
        dfs(to, idx);
        if(this->low[to] >= this->ord[idx]) {
          bc.emplace_back();
          for(;;) {
            auto e = tmp.back();
            bc.back().emplace_back(e);
            tmp.pop_back();
            if(e.first == min(idx, to) && e.second == max(idx, to)) {
              break;
            }
          }
        }
      }
    }
  }
 
  void build() override {
    LL::build();
    used.assign(this->g.size(), 0);
    for(int i = 0; i < used.size(); i++) {
      if(!used[i]) dfs(i, -1);
    }
  }
};

ll N, M, K;

ll ans = 1;

ll dp[101][101];
ll beki(ll a, ll b) {
    if(b == 0) return 1;
    ll ret = beki(a, b / 2);
    ret = ret * ret % mod;
    if(b & 1) ret = ret * a % mod;
    return ret;
}
void initialize() {
  dp[0][0] = 1;
  for(ll c = 1; c <= 100; c++) {
    for(ll before = 0; before <= 100; before++) {
      for(ll after = before; after <= 100; after++) {
        dp[c][after] += dp[c-1][before];
        dp[c][after] %= mod;
      }
    }
  }
}

ll circuit(ll x) {
    ll tmp = 0;
    for(ll i = 0; i < x; i++) {
        ll g = __gcd(x, i);
        tmp += beki(K, g);
        tmp %= mod;
    }
    tmp *= beki(x, mod - 2);
    tmp %= mod;
    return tmp;
}

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> M >> K;
    initialize();
    UnWeightedGraph g(N);
    for(int i = 0; i < M; i++) {
      int a, b;
      cin >> a >> b;
      a--;
      b--;
      g[a].push_back(b);
      g[b].push_back(a);
    }
    BiConnectedComponents<UnWeightedGraph> BCC(g);
    BCC.build();
    for(auto bcc : BCC.bc) {
        if(bcc.size() == 1) {
            ans *= K;
            ans %= mod;
            continue;
        }
        set<ll> vertex;
        for(auto tmp : bcc) {
            vertex.insert(tmp.first);
            vertex.insert(tmp.second);
        }
        if(vertex.size() == bcc.size()) {
            ans *= circuit(vertex.size());
            ans %= mod;
        } else {
            ans *= dp[K][bcc.size()];
            ans %= mod;
        }
    }
    cout << ans << endl;
    /*
    for(auto tmp : BCC.bc) {
      cerr << "------" << endl;
      for(auto tmp2 : tmp) {
        cerr << tmp2.first << " " << tmp2.second << endl;
      }
    }
    */
    return 0;
}


Measured memory_bytes: 384