#include <bits/stdc++.h>
#define err(args...) {}
#ifdef DEBUG
#include "_debug.cpp"
#endif
using namespace std;
using ll = long long;
using ld = long double;
template <typename T> using lim = numeric_limits<T>;
template <typename T> istream& operator>>(istream& is, vector<T>& a) { for(T& x : a) { is >> x; } return is; }
template <bool Directed, typename TEdge> struct graph {
    using EType = TEdge;
    vector<TEdge> edges;
    vector<vector<int>> adj;
    graph(int n) : adj(n + 1) {}
    graph(int n, int m) : graph(n) { edges.reserve(m << not Directed); }
    TEdge& operator()(int i) { return edges[i]; }
    vector<int>& operator[](int u) { return adj[u]; }
    int size() { return adj.size() - 1; }
    void add_edge(const TEdge& e) {
        adj[e.u].push_back(edges.size());
        edges.push_back(e);
        if(not Directed) {
            adj[e.v].push_back(edges.size());
            edges.push_back(e.reverse());
        }
    }
};
struct edge {
    int u, v;
    edge reverse() const { return {v, u}; }
    friend ostream& operator<<(ostream& os, const edge& e) {
        os << "(" << e.u << ", " << e.v << ")";
        return os;
    }
};
pair<vector<int>, vector<vector<int>>> find_bccs(graph<0, edge>& g) {
    vector<int> vis(g.adj.size()), low(g.adj.size()), cut_node(g.adj.size()), s;
    vector<vector<int>> bccs = {};
    int timer = 1;
    function<void(int, int)> dfs = [&](int u, int from) {
        vis[u] = low[u] = timer++;
        int n_children = 0;
        for(int i : g[u]) {
            if(not vis[g(i).v]) {
                s.push_back(i & ~1);
                dfs(g(i).v, u);
                n_children++;
                if(vis[u] <= low[g(i).v]) {
                    cut_node[u] = true;
                    bccs.push_back(vector<int>());
                    do {
                        bccs.back().push_back(s.back()), s.pop_back();
                    } while(bccs.back().back() != (i & ~1));
                }
                low[u] = min(low[u], low[g(i).v]);
            } else if(g(i).v != from and vis[u] > vis[g(i).v]) {
                s.push_back(i & ~1);
                low[u] = min(low[u], vis[g(i).v]);
            }
        }
        cut_node[u] &= from or n_children > 1;
    };
    for(int u = 1; u <= g.size(); u++) if(not vis[u]) {
        dfs(u, 0);
    }
    return {cut_node, bccs};
}
template <typename T> constexpr T fpow_eq(T& x, ll y, T identity = 1) {
    for(; y > 0; x *= x, y >>= 1) {
        if(y & 1) {
            identity *= x;
        }
    }
    return x = identity;
}
template <typename T> constexpr T fpow(T x, ll y, T identity = 1) { return fpow_eq(x, y, identity); }
#ifdef __TOTIENT_INCLUDED_
template <int M, int PHI_M = phi(M)> struct modint {
#else
template <int M, int PHI_M> struct modint {
#endif
    static constexpr int MOD = M;
    int val;
    constexpr modint() : val(0) {}
    constexpr modint(int val) : val(val % M) { val += val < 0 ? M : 0; }
    constexpr modint(long long val) : modint(int(val % M)) {}
    constexpr modint(const modint& m) : val(m.val) {}
    constexpr explicit operator int() const { return val; }
    constexpr bool operator==(const modint& y) const { return val == y.val; }
    constexpr bool operator!=(const modint& y) const { return val != y.val; }
    constexpr bool operator< (const modint& y) const { return val <  y.val; }
    constexpr bool operator<=(const modint& y) const { return val <= y.val; }
    constexpr bool operator> (const modint& y) const { return val >  y.val; }
    constexpr bool operator>=(const modint& y) const { return val >= y.val; }
    constexpr modint& operator=(const modint& y) { val = y.val; return *this; }
    constexpr modint& operator+=(const modint& y) { val += y.val; val -= val >= M ? M : 0; return *this; }
    constexpr modint& operator-=(const modint& y) { val -= y.val; val += val <  0 ? M : 0; return *this; }
    constexpr modint& operator*=(const modint& y) { val = ll(val) * y.val % M; return *this; }
    constexpr modint& operator/=(const modint& y) { val = ll(val) * fpow(y, PHI_M - 1).val % M; return *this; }
    constexpr modint& operator^=(ll y) { fpow_eq(*this, y); return *this; }
    constexpr modint operator+(const modint& y) const { return modint(val) += y; }
    constexpr modint operator-(const modint& y) const { return modint(val) -= y; }
    constexpr modint operator*(const modint& y) const { return modint(val) *= y; }
    constexpr modint operator/(const modint& y) const { return modint(val) /= y; }
    constexpr modint operator^(ll y) const { return modint(val) ^= y; }
    constexpr modint operator-() const { return modint(0) -= *this; }
    constexpr modint operator~() const { return modint(1) /= *this; }
    constexpr modint& operator++() { val = val == M - 1 ? 0 : val + 1; return *this; }
    constexpr modint& operator--() { val = val == 0 ? M - 1 : val - 1; return *this; }
    constexpr modint operator++(int) { modint m = *this; ++(*this); return m; }
    constexpr modint operator--(int) { modint m = *this; --(*this); return m; }
    friend constexpr modint operator+(long long x, const modint& y) { return modint(x) + y; }
    friend constexpr modint operator*(long long x, const modint& y) { return modint(x) * y; }
    friend constexpr modint operator-(long long x, const modint& y) { return modint(x) - y; }
    friend constexpr modint operator/(long long x, const modint& y) { return modint(x) / y; }
    friend ostream& operator<<(ostream& os, const modint& m) { return os << m.val; }
    friend istream& operator>>(istream& is, modint& m) { ll val; is >> val; m = modint(val); return is; }
};
constexpr int M = 1'000'000'007;
using mint = modint<M, M - 1>;
mint operator""_m(unsigned long long int x) { return mint(ll(x)); }
#ifndef __COMBINATIONS_INCLUDED_
#define __COMBINATIONS_INCLUDED_
template <typename T = mint> T fact(int n) {
    static vector<T> fac = {1};
    while(fac.size() <= n) {
        fac.push_back(fac.back() * int(fac.size()));
    }
    return fac[n];
}
template <typename T = mint> T fact_inv(int n) {
    static vector<T> inv_fac = {1};
    while(inv_fac.size() <= n) {
        inv_fac.push_back(inv_fac.back() / int(inv_fac.size()));
    }
    return inv_fac[n];
}
template <typename T = mint> T C(int n, int k) {
    assert(n >= 0), assert(k >= 0);
    return k <= n ? fact<T>(n) * fact_inv<T>(k) * fact_inv<T>(n - k) : 0;
}
#endif
template <typename T = mint> T C_nonnegative(int n, int k) {
    return k == 0 ? n == 0 : C<T>(n + k - 1, k - 1);
}
template <typename T = mint> T C_nonnegative(int n, int k, int ub) {
    T ans = C_nonnegative<T>(n, k);
    T sgn = -1;
    for(int i = 1; i <= k and n - ub * i >= 0; i++) {
        ans += sgn * C<T>(k, i) * C_nonnegative<T>(n - ub * i, k);
        sgn *= -1;
    }
    return ans;
}
template <typename T = mint> T C_positive(int n, int k) {
    return C_nonnegative(n - k, k);
}
template <typename T = mint> T C_positive(int n) {
    return n == 0 ? 1 : T(2) ^ (n - 1);
}
template <typename T = mint> T multi_C(int n, int k) {
    return C_nonnegative<T>(k, n);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    graph<0, edge> g(n, m);
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g.add_edge({u, v});
    }
    mint ans = 1;
    for(auto& bcc : find_bccs(g).second) {
        set<int> bcc_nodes;
        for(int i : bcc) {
            bcc_nodes.insert({g(i).u, g(i).v});
        }
        if(bcc.size() == bcc_nodes.size()) {
            mint ways = 0;
            for(int j = 0; j < bcc.size(); j++) {
                ways += mint(k) ^ __gcd(j, int(bcc.size()));
            }
            ans *= ways / int(bcc.size());
        } else {
            ans *= multi_C(k, bcc.size());
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256