#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
const int mod = (int)1e9 + 7;

const int root = 646;

const int root_1 = 208611436;

const int root_pw = 1<<20;

int mult(int a, int b) {
    return (1LL * a * b) % mod;
}

int pw(int a, int b) {
    if (b == 0) return 1;
    if (b & 1) return mult(a, pw(a, b - 1));
    int res = pw(a, b / 2);
    return mult(res, res);
}

int sub(int a, int b) {
    int s = a - b;
    if (s < 0) s += mod;
    return s;
}

int sum(int a, int b) {
    int s = a + b;
    if (s >= mod) s -= mod;
    return s;
}

const int maxP = 3 * (int)1e4 + 100;

int fact[maxP], invfact[maxP], inv[maxP];

void init() {
    inv[1] = invfact[1] = invfact[0] = fact[0] = fact[1] = 1;
    for (int i = 2; i < maxP; i++) {
        fact[i] = mult(fact[i - 1], i);
        inv[i] = mult(inv[mod % i], mod - mod / i);
        invfact[i] = mult(invfact[i - 1], inv[i]);
    }
}

int cnk(int n, int k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return mult(fact[n], mult(invfact[k], invfact[n - k]));
}

int invNumber(int a) {
    return pw(a, mod - 2);
}

const int maxN = 105;
int n, m, k;
bool f[maxN][maxN];
bool used[maxN];
bool was[maxN];
int h[maxN];
void dfs(int v) {
    used[v] = true;
    for (int to = 1; to <= n; to++) {
        if (used[to]) continue;
        if (!f[v][to]) continue;
        dfs(to);
    }
}

int tin[maxN];
int tout[maxN];
int timer = 0;
int par[maxN];
void dfs_sec(int v) {
    used[v] = true;
    tin[v] = ++timer;
    for (int j = 1; j <= n; j++) {
        if (j == v || !f[j][v]) continue;
        if (used[j]) continue;
        par[j] = v;
        h[j] = h[v] + 1;
        dfs_sec(j);
    }
    tout[v] = ++timer;
}

bool is_par(int a, int batya) {
    return (tin[batya] <= tin[a] && tout[a] <= tout[batya]);
}

bool mark[maxN];
bool bad[maxN][maxN];
bool cur[maxN];
bool pt[maxN];
bool already[maxN];
int nec(int x) {
    int ans = 0;
    for (int shift = 1; shift <= x; shift++) {
        ans = sum(ans, pw(k, __gcd(shift, x)));
    }
    return mult(ans, pw(x, mod - 2));
}
int U = 0;
int vvvv[maxN][maxN];
int solve(vector < int >& cmp) {
    memset(mark, 0, sizeof mark);
    int ans = 1;
    int edges = 0;
    for (int a = 0; a < cmp.size(); a++) {
        for (int b = a + 1; b < cmp.size(); b++) {
            edges += f[cmp[a]][cmp[b]];
            vvvv[cmp[a]][cmp[b]] = vvvv[cmp[b]][cmp[a]] = true;
        }
    }
    U += edges;
    if (edges == 0) return ans;
    if (edges == cmp.size()) {
        ans = mult(ans, nec(edges));
        return ans;
    }
    timer = 0;
    memset(used, 0, sizeof used);
    dfs_sec(cmp[0]);
    bool has = false;
    for (int x : cmp) {
        if (has) break;
        for (int y : cmp) {
            if (x == y) continue;
            if (par[x] == y || par[y] == x) continue;
            if (h[x] < h[y]) swap(x, y);
            if (!f[x][y]) continue;
            int inx = x;
            int iny = y;
            while (h[x] != h[y]) {
                if (mark[x]) {
                    has = true;
                    break;
                }
                mark[x] = true;
                x = par[x];
            }
            int lca = x;
            while (!is_par(y, lca)) lca = par[lca];
            while (x != lca) {
                if (mark[x]) {
                    has = true;
                    break;
                }
                mark[x] = true;
                x = par[x];
            }
            while (y != lca) {
                if (mark[y]) {
                    has = true;
                    break;
                }
                mark[y] = true;
                y = par[y];
            }
            if ((h[inx] - h[lca] + h[iny] - h[lca] + 1) % 2 == 0) {
                has = true;
            }
        }
    }
    if (has) {
        ans = mult(ans, cnk(edges + k - 1, k - 1));
    }
    else {
        assert(edges >= 3);
        int tot_ways = cnk(edges + k - 1, k - 1);
        int ways_diff = cnk(k, edges);
        ans = mult(ans, sum(tot_ways, ways_diff));
    }
    return ans;
}
bool orig[105][105];
bool here[105];
int stupid_solve(vector < int > cmp) {
    memset(cur, 0, sizeof cur);
    for (int rrr : cmp) cur[rrr] = true;
    for (int v : cmp) {
        bool hs = false;
        for (int r = 1; r <= n; r++) {
            f[v][r] = f[r][v] = false;
        }
        for (int u : cmp) {
            if (u == v) continue;
            memset(used, 0, sizeof used);
            dfs(u);
            for (int j = 1; j <= n; j++) {
                if (!used[j] && cur[j] && (j != v) && (j != u)) {
                    bad[u][j] = true;
                    hs = true;
                }
            }
        }
        if (hs) {
            vector < vector < int > > all;
            memset(here, 0, sizeof here);
            for (int p = 1; p <= n; p++) {
                if (p == v) continue;
                if (cur[p] && !here[p]) {
                    memset(used, 0, sizeof used);
                    dfs(p);
                    vector < int > nw;
                    for (int j = 1; j <= n; j++) {
                        if (used[j] && cur[j]) {
                            here[j] = true;
                            nw.emplace_back(j);
                        }
                    }
                    nw.emplace_back(v);
                    all.emplace_back(nw);
                }
            }
            for (int r = 1; r <= n; r++) {
                f[v][r] = orig[v][r];
                f[r][v] = orig[r][v];
            }
            int ccc = 1;
            for (auto& it : all) {
                ccc = mult(ccc, stupid_solve(it));
            }
            return ccc;
        }
        for (int r = 1; r <= n; r++) {
            f[v][r] = orig[v][r];
            f[r][v] = orig[r][v];
        }
    }
    return solve(cmp);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("input.txt", "r", stdin);
    init();
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        f[a][b] = f[b][a] = true;
    }
    int ans = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (f[i][j]) {
                f[i][j] = f[j][i] = 0;
                memset(used, 0, sizeof used);
                dfs(i);
                if (!used[j]) {
                    ans = mult(ans, k);
                    continue;
                }
                else {
                    f[i][j] = f[j][i] = 1;
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) orig[i][j] = f[i][j];
    for (int i = 1; i <= n; i++) {
        if (was[i]) continue;
        vector < int > cmp;
        memset(used, 0, sizeof used);
        dfs(i);
        memset(cur, 0, sizeof cur);
        for (int j = 1; j <= n; j++) {
            if (used[j]) {
                was[j] = true;
                cur[j] = true;
                cmp.emplace_back(j);
            }
        }
        ans = mult(ans, stupid_solve(cmp));
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 640