/*
11 12 48
3 1
8 2
4 9
5 4
1 6
2 9
8 3
10 8
4 10
8 6
11 7
1 8
*/
#include <bits/stdc++.h>
using namespace std; using ll = long long; using ld = long double; using pii = pair<int, int>; const int N = 100 + 5, M = 1e9 + 7, INF = 0x3f3f3f3f; const ll LNF = 0x3f3f3f3f3f3f3f3f; void Main();
void debug() { cerr << endl; } template <typename T, typename... Ts> void debug(T x, Ts... y) { cerr << "\033[31m" << x << "\033[0m"; if (sizeof...(y) > 0) cerr << ' '; debug(y...); } template <typename T> void debug(const T& a, int l, int r, char c) { for (int i = l; i <= r; ++i) cerr << "\033[31m" << a[i] << "\033[0m" << (i == r ? '\n' : c); }
void print() { cout << '\n'; } template <typename T, typename... Ts> void print(T x, Ts... y) { cout << x; if (sizeof...(y) > 0) cout << ' '; print(y...); } template <typename T> void print(const T& a, int l, int r, char c) { for (int i = l; i <= r; ++i) cout << a[i] << (i == r ? '\n' : c); }
void input() {} template <typename T, typename... Ts> void input(T& x, Ts&... y) { cin >> x; input(y...); } template <typename T> void input(T* a, int l, int r) { for (int i = l; i <= r; ++i) cin >> a[i]; } template <typename T> void input(vector<T>& a, int l, int r) { for (int i = l; i <= r; ++i) cin >> a[i]; }
template <typename T> void Max(T& a, T b) { if (a < b) a = b; } template <typename T> void Min(T& a, T b) { if (a > b) a = b; } template <typename T> void Add(T& a, T b) { a += b; if (a > M) a -= M; if (a < 0) a += M; } template <typename T> void Mul(T& a, T b) { a = a * b % M; } template <typename T> T Mod(T a) { return (a % M + M) % M; }
int main(int argc, char** argv) {
    ios::sync_with_stdio(0); cin.tie(0); /* cout << setprecision(10) << fixed; */
#ifdef Zmm
    if (argc) { freopen((string(*(argv)).substr(2, string(*(argv)).size() - 6) + string(".cpp")).c_str(), "r", stdin); string x; cin >> x; }
#endif
    Main();
}
ll qpow(ll a, ll b, ll mod = numeric_limits<ll>::max()) { ll ret = 1; for (; b; b >>= 1, a = a * a % mod) if (b & 1) ret = a * ret % mod; return ret; }
int C[N + N][N + N];
void getC(int n) {
    C[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % M;
    }
}
int ecnt[N];
template<int N>
struct VDCC {
    struct edge {
        int u, v;
    };
    vector<edge> G[N];
    vector<int> dccs[N];
    int dfn[N], low[N], tot, dcc[N], bridge, dcnt;
    bitset<N> iscut;
    void init(int n) {
        bridge = 0, dcnt = 0, tot = 0;
        for (int i = 1; i <= n; i++) G[i].clear(), dfn[i] = 0, dcc[i] = 0, iscut[i] = false;
    }
    void add(int u, int v) {
        G[u].push_back({u, v});
        G[v].push_back({v, u});
    }
    stack<edge> s;
    void dfs(int u, int fa) {
        dfn[u] = low[u] = ++tot;
        int child = 0;
        for (edge& e : G[u]) {
            if (!dfn[e.v]) {
                s.push(e);
                child++;
                dfs(e.v, u);
                low[u] = min(low[u], low[e.v]);
                if (dfn[u] <= low[e.v]) {
                    if (dfn[u] < low[e.v]) bridge++;
                    iscut[u] = true;
                    dccs[++dcnt].clear();
                    while (true) {
                        edge t = s.top();
                        ++ecnt[dcnt];
                        s.pop();
                        if (dcc[t.u] != dcnt) {
                            dccs[dcnt].push_back(t.u);
                            dcc[t.u] = dcnt;
                        }
                        if (dcc[t.v] != dcnt) {
                            dccs[dcnt].push_back(t.v);
                            dcc[t.v] = dcnt;
                        }
                        if (t.u == e.u && t.v == e.v) break;
                    }
                }
            } else if (e.v != fa && dfn[u] > dfn[e.v]) {
                low[u] = min(low[u], dfn[e.v]);
                s.push(e);
            }
        }
        if (fa == u && child == 1) iscut[u] = false;
    }
    void tarjan(int n) {
        for (int i = 1; i <= n; i++)
            if (!dfn[i]) dfs(i, i);
    }
};
VDCC<55> V;
void Main() {
    int n, m, k;
    input(n, m, k);
    V.init(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        input(u, v);
        V.add(u, v);
    }
    V.tarjan(n);
    ll ans = 1;
    getC(200);
    for (int i = 1; i <= V.dcnt; ++i) {
        if (ecnt[i] == 1) {
            ans = ans * k % M;
        } else if ((int)V.dccs[i].size() == ecnt[i]) {
            ll sum = 0;
            for (int j = 0; j < ecnt[i]; ++j) {
                sum = (sum + qpow(k, __gcd(j, ecnt[i]), M)) % M;
            }
            ans = ans * sum % M * qpow(ecnt[i], M - 2, M) % M;
        } else {
            ans = ans * C[ecnt[i] + k - 1][k - 1] % M;
        }
    }
    print(ans);
}

Measured memory_bytes: 3816