#include <algorithm>
#include <cassert>
#include <cmath>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
using ll = long long;
using namespace std;
template <class T, class U> inline void chmax(T & a, U const & b) { a = max<T>(a, b); }
template <class T, class U> inline void chmin(T & a, U const & b) { a = min<T>(a, b); }

template <int32_t MOD>
struct mint {
    int64_t value;  // faster than int32_t a little
    mint() = default;  // value is not initialized
    mint(int64_t value_) : value(value_) {}  // assume value is in proper range
    inline mint<MOD> operator + (mint<MOD> other) const { int64_t c = this->value + other.value; return mint<MOD>(c >= MOD ? c - MOD : c); }
    inline mint<MOD> operator * (mint<MOD> other) const { int64_t c = this->value * int64_t(other.value) % MOD; return mint<MOD>(c < 0 ? c + MOD : c); }
    inline mint<MOD> & operator += (mint<MOD> other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; }
    inline mint<MOD> & operator *= (mint<MOD> other) { this->value = this->value * int64_t(other.value) % MOD; if (this->value < 0) this->value += MOD; return *this; }
    mint<MOD> pow(uint64_t k) const {
        mint<MOD> x = *this, y = 1;
        for (; k; k >>= 1) {
            if (k & 1) y *= x;
            x *= x;
        }
        return y;
    }
    mint<MOD> inv() const { return pow(MOD - 2); }  // MOD must be a prime
    inline mint<MOD> operator / (mint<MOD> other) const { return *this *  other.inv(); }
};

template <int32_t MOD>
mint<MOD> fact(int n) {
    static vector<mint<MOD> > memo(1, 1);
    while (n >= memo.size()) {
        memo.push_back(memo.back() * mint<MOD>(memo.size()));
    }
    return memo[n];
}
template <int32_t PRIME>
mint<PRIME> inv_fact(int n) {
    static vector<mint<PRIME> > memo;
    if (memo.size() <= n) {
        int l = memo.size();
        int r = n * 1.3 + 100;
        memo.resize(r);
        memo[r - 1] = fact<PRIME>(r - 1).inv();
        for (int i = r - 2; i >= l; -- i) {
            memo[i] = memo[i + 1] * (i + 1);
        }
    }
    return memo[n];
}

/**
 * @tparam MOD must be a prime
 * @note O(n log n) at first time, otherwise O(1)
 */
template <int32_t MOD>
mint<MOD> choose(int n, int r) {
    assert (0 <= r and r <= n);
    return fact<MOD>(n) * inv_fact<MOD>(n - r) * inv_fact<MOD>(r);
}

/**
 * @brief 2-node-connected components decomposition
 * @param g an adjacent list of the simple undirected graph
 * @note O(V + E)
 * @return list of (list of edges in the component)
 */
vector<vector<pair<int, int> > > decompose_to_two_node_connected_components(vector<vector<int> > const & g) {
    int n = g.size();
    vector<int> ord(n, -1);
    vector<int> low(n, -1);
    vector<bool> used(n);
    vector<vector<pair<int, int> > > components;
    stack<pair<int, int> > stk;
    int k = 0;
    function<void (int, int)> go = [&](int i, int parent) {
        used[i] = true;
        ord[i] = k ++;
        low[i] = ord[i];
        for (auto j : g[i]) if (j != parent) {
            if (ord[j] < ord[i]) {
                stk.emplace(minmax({ i, j }));
            }
            if (used[j]) {
                chmin(low[i], ord[j]);
            } else {
                go(j, i);
                chmin(low[i], low[j]);
                if (low[j] >= ord[i]) {
                    components.emplace_back();
                    while (true) {
                        pair<int, int> e = stk.top();
                        components.back().push_back(e);
                        stk.pop();
                        if (e == minmax({ i, j })) {
                            break;
                        }
                    }
                }
            }
        }
    };
    REP (i, n) if (not used[i]) {
        go(i, -1);
    }
    return components;
}

/**
 * @brief enumerate primes in [2, n) with O(n log log n)
 */
vector<int> list_primes(int n) {
    vector<bool> is_prime(n, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i *(ll) i < n; ++ i)
        if (is_prime[i])
            for (int k = 2 * i; k < n; k += i)
                is_prime[k] = false;
    vector<int> primes;
    for (int i = 2; i < n; ++ i)
        if (is_prime[i])
            primes.push_back(i);
    return primes;
}

/**
 * @note the last number of primes must be >= sqrt n
 */
map<ll, int> prime_factorize(ll n, vector<int> const & primes) {
    map<ll, int> result;
    for (int p : primes) {
        if (n < p *(ll) p) break;
        while (n % p == 0) {
            result[p] += 1;
            n /= p;
        }
    }
    if (n != 1) result[n] += 1;
    return result;
}

/**
 * @note if n < 10^9, d(n) < 1200 + a
 */
vector<ll> list_divisors(ll n, vector<int> const & primes) {
    vector<ll> result;
    result.push_back(1);
    for (auto it : prime_factorize(n, primes)) {
        ll p; int k; tie(p, k) = it;
        int size = result.size();
        REP (y, k) {
            REP (x, size) {
                result.push_back(result[y * size + x] * p);
            }
        }
    }
    return result;
}

/**
 * @note using Polya enumeration theorem
 * @note factorization + O(d(n)^2 + sqrt n)
 */
template <int MOD>
mint<MOD> count_cycle_coloring(ll n, ll k) {
    auto primes = list_primes(sqrt(n) + 3);
    map<ll, int> factors = prime_factorize(n, primes);
    vector<ll> divs = list_divisors(n, primes);
    mint<MOD> cnt = 0;
    for (ll div : divs) {
        ll e = div;  // Euler's phi of div
        for (auto it : factors) {
            int p = it.first;
            if (div % p == 0) {
                e = e / p * (p - 1);
            }
        }
        cnt += mint<MOD>(k).pow(n / div) * e;
    }
    return cnt / n;
}

constexpr int MOD = 1e9 + 7;
mint<MOD> solve(int n, int m, int k, vector<vector<int> > const & g) {
    auto components = decompose_to_two_node_connected_components(g);
    mint<MOD> cnt = 1;
    for (auto const & edges : components) {
        set<int> nodes;
        for (auto edge : edges) {
            nodes.insert(edge.first);
            nodes.insert(edge.second);
        }
        int max_degree = 0;
        for (int i : nodes) {
            int degree = 0;
            for (int j : g[i]) if (nodes.count(j)) {
                ++ degree;
            }
            chmax(max_degree, degree);
        }
        if (max_degree == 0) {
            assert (false);
        } else if (max_degree == 1) {
            cnt *= k;
        } else if (max_degree == 2) {
            cnt *= count_cycle_coloring<MOD>(edges.size(), k);
        } else {
            cnt *= choose<MOD>(edges.size() + k - 1, k - 1);
        }
    }
    return cnt;
}

int main() {
    int n, m, k; cin >> n >> m >> k;
    vector<vector<int> > g(n);
    REP (i, m) {
        int a, b; cin >> a >> b;
        -- a; -- b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    cout << solve(n, m, k, g).value << endl;
    return 0;
}


Measured memory_bytes: 256