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

const int mod = 1e9 + 7;

int exp(int x, int n) {
    int ret = 1;
    while(n) {
        if(n & 1) ret = 1LL * ret * x % mod;
        x = 1LL * x * x % mod;
        n >>= 1;
    }
    return ret;
}
int inv(int x) {
    return exp(x, mod - 2);
}
int fact[222], invf[222];
int comb(int n, int k) {
    return 1LL * fact[n] * invf[k] % mod * invf[n - k] % mod;
}
int H(int n, int k) {
    return comb(n + k - 1, k);
}

int N, M, K;
vector<int> adj[55], U, V;
int tin[55], bck[55], id[111], timer, bcnt;
stack<int> stk;

void dfs(int u, int fe) {
    tin[u] = timer++;
    bck[u] = tin[u];

    for(int i = 0; i < adj[u].size(); i++) {
        int e = adj[u][i];
        int v = U[e] + V[e] - u;
        if(e == fe) continue;
        if(tin[v] == -1) {
            stk.push(e);
            dfs(v, e);
            bck[u] = min(bck[u], bck[v]);
            if(bck[v] >= tin[u]) {
                while(1) {
                    int t = stk.top(); stk.pop();
                    id[t] = bcnt;
                    if(t == e) break;
                }
                bcnt++;
            }
        }
        else if(tin[v] < tin[u]) {
            stk.push(e);
            bck[u] = min(bck[u], tin[v]);
        }
    }
}

int prec[55];

int main() {
    fact[0] = 1;
    for(int i = 1; i < 222; i++) {
        fact[i] = 1LL * fact[i - 1] * i % mod;
    }
    for(int i = 0; i < 222; i++) {
        invf[i] = inv(fact[i]);
    }

    scanf("%d %d %d", &N, &M, &K);

    for(int i = 0; i < M; i++) {
        int u, v; scanf("%d %d", &u, &v);
        u--; v--;

        adj[u].push_back(i);
        adj[v].push_back(i);
        U.push_back(u);
        V.push_back(v);
    }

    memset(tin, -1, sizeof(tin));
    for(int i = 0; i < N; i++) if(tin[i] == -1) {
        dfs(i, -1);
    }

    for(int i = 1; i <= N; i++) {
        vector<int> cnt(i + 1, 0);

        for(int j = 1; j <= i; j++) {
            if(i % j) continue;

            cnt[j] += exp(K, j);
            cnt[j] %= mod;
            prec[i] += 1LL * cnt[j] * inv(j) % mod;
            prec[i] %= mod;
            for(int k = 2 * j; k <= i; k += j) {
                cnt[k] += mod - cnt[j];
                cnt[k] %= mod;
            }
        }
    }

    int ans = 1;
    for(int i = 0; i < bcnt; i++) {
        vector<int> chk(N, 0);
        int vcnt = 0;
        int ecnt = 0;
        for(int j = 0; j < M; j++) {
            if(id[j] == i) {
                if(!chk[ U[j] ]) {
                    chk[ U[j] ] = 1;
                    vcnt++;
                }
                if(!chk[ V[j] ]) {
                    chk[ V[j] ] = 1;
                    vcnt++;
                }
                ecnt++;
            }
        }
        if(vcnt == ecnt) {
            //cout << vcnt << endl;
            ans = 1LL * ans * prec[vcnt] % mod;
        }
        else if(ecnt == 1) ans = 1LL * ans * K % mod;
        else ans = 1LL * ans * H(K, ecnt) % mod;
    }
    printf("%d", ans);
}
