#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
#define SZ(x) ((int) (x).size())
using namespace std;

const int MOD = (int) 1e9 + 7;
const int NMAX = 55, MMAX = 105;

int fact[7 * MMAX], invFact[7 * MMAX];

int Pow(int x, int y) {
    int ret = 1;
    for (; y > 0; y /= 2) {
        if (y & 1) {
            ret = (int64_t) ret * x % MOD;
        }
        x = (int64_t) x * x % MOD;
    }
    return ret;
}

void precalc(int n) {
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) {
        fact[i] = (int64_t) fact[i - 1] * i % MOD;
    }
    invFact[n] = Pow(fact[n], MOD - 2);
    for (int i = n - 1; i >= 0; --i) {
        invFact[i] = (int64_t) invFact[i + 1] * (i + 1) % MOD;
    }
}

int comb(int n, int k) {
    return (int64_t) fact[n] * invFact[n - k] % MOD * invFact[k] % MOD;
}

vector<int> G[NMAX];
int node1[MMAX], node2[MMAX];
bool used[NMAX];

vector<vector<pair<int, int>>> bicomps;

int level[NMAX], minlvl[NMAX];

vector<pair<int, int>> stk;

void popStack(int node, int son) {
    vector<pair<int, int>> comp;
    int n1, n2;
    do {
        comp.push_back(stk.back());
        n1 = stk.back().first;
        n2 = stk.back().second;
        stk.pop_back();
    } while (n1 != node || n2 != son);
    bicomps.push_back(comp);
}

void dfs(int node, int prevEdge) {
    used[node] = 1;
    minlvl[node] = level[node];

    for (int e: G[node]) {
        if (e == prevEdge) {
            continue;
        }
        int to = node1[e] ^ node2[e] ^ node;
        if (used[to]) {
            if (level[to] < level[node]) {
                stk.push_back(make_pair(node, to));
            }
            minlvl[node] = min(minlvl[node], level[to]);
        } else {
            level[to] = level[node] + 1;
            stk.push_back(make_pair(node, to));
            dfs(to, e);
            minlvl[node] = min(minlvl[node], minlvl[to]);

            if (minlvl[to] >= level[node]) {
                popStack(node, to);
            }
        }
    }
}

int freq[NMAX];

int gcd(int a, int b) {
    while (b) {
        int c = a % b;
        a = b;
        b = c;
    }
    return a;
}

int cyclicShifts(int len, int k) {
    int ans = 0;
    for (int shift = 1; shift <= len; shift++) {
        ans += Pow(k, gcd(shift, len));
        ans %= MOD;
    }
    ans = (int64_t) ans * Pow(len, MOD - 2) % MOD;
    return ans;
}

int solve(const vector<pair<int, int>>& comp, int k) {
    int ans = 1;
    int cnt = 0;
    for (const pair<int, int>& e: comp) {
        cnt += freq[e.first] == 0;
        cnt += freq[e.second] == 0;
        freq[e.first]++;
        freq[e.second]++;
    }

    if (cnt == SZ(comp)) {
        ans = cyclicShifts(cnt, k);
    } else {
        ans = comb(SZ(comp) + k - 1, k - 1);
    }

    for (const pair<int, int>& e: comp) {
        freq[e.first]--;
        freq[e.second]--;
    }
    return ans;
}

int main()
{
    #ifdef LOCAL_RUN
    freopen("task.in", "r", stdin);
    freopen("task.out", "w", stdout);
    #endif // LOCAL_RUN
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m, k;
    cin >> n >> m >> k;

    precalc(3 * (m + k));

    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        G[x].push_back(i);
        G[y].push_back(i);
        node1[i] = x;
        node2[i] = y;
    }

    for (int node = 1; node <= n; ++node) {
        if (!used[node]) {
            dfs(node, -1);
        }
    }

    int ans = 1;
    for (const vector<pair<int, int>>& comp: bicomps) {
        ans = (int64_t) ans * solve(comp, k) % MOD;
    }

    cout << ans << '\n';
}

Measured memory_bytes: 256