#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>
#include <set>
#include <string>
#include <iostream>
#include <cassert>
#include <cmath>
using namespace std;

const int MOD = 1e9 + 7;

long long gcd(long long a, long long b) {
        while (b) {
                a %= b;
                swap(a, b);
        }
        return a;
}

long long ModPow(long long x, long long n, long long m) {
        long long res = 1;
        while (n > 0) {
                if (n & 1) res = res * x % m;
                x = x * x % m;
                n >>= 1;
        }
        return res;
}

long long Inv(long long x, long long m) {
        return ModPow(x, m - 2, m);
}

const int N = 5000001;
long long fact[N];
long long invfact[N];
long long inv[N];
void init() {
        fact[0] = fact[1] = 1;
        for (int i = 2; i < N; i ++) fact[i] = fact[i - 1] * i % MOD;
        inv[1] = 1;
        for (int i = 2; i < N; i ++) inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
        invfact[0] = invfact[1] = 1;
        for (int i = 2; i < N; i ++) invfact[i] = invfact[i - 1] * inv[i] % MOD;
}
long long C(long long n, long long r) {
        if (n < 0 || r < 0 || n < r) return 0;
        return fact[n] * invfact[n - r] % MOD * invfact[r] % MOD;
}

struct BiconnectedComponent {
        vector<int> ord, low;
        vector<bool> used;
        vector<vector<int>> g;
        vector<vector<pair<int, int>>> bc;
        vector<pair<int, int>> tmp;
        int n, k = 0;
        BiconnectedComponent(const vector<vector<int>> &g) : g(g) {
                n = g.size();
                ord.resize(n, -1);
                low.resize(n, -1);
                used.resize(n, false);
        }
        void dfs(int u, int prev) {
                used[u] = true;
                ord[u] = k ++;
                low[u] = ord[u];
                int cnt = 0;
                for (auto v : g[u]) if (v != prev) {
                        if (ord[v] < ord[u]) { 
                                tmp.emplace_back(min(u, v), max(u, v));
                        }
                        if (!used[v]) {
                                cnt ++;
                                dfs(v, u);
                                low[u] = min(low[u], low[v]);
                                if (low[v] >= ord[u]) {
                                        bc.push_back({});
                                        while (true) {
                                                pair<int, int> e = tmp.back();
                                                bc.back().emplace_back(e);
                                                tmp.pop_back();
                                                if (min(u, v) == e.first && max(u, v) == e.second) {
                                                        break;
                                                }
                                        }
                                }
                        } else {
                                low[u] = min(low[u], ord[v]);
                        }
                }
        }
};

int main() {
        init();
        int n, m, k;
        scanf("%d%d%d", &n, &m, &k);
        vector<vector<int>> g(n);
        for (int i = 0; i < m; i ++) {
                int a, b;
                scanf("%d%d", &a, &b);
                a --, b --;
                g[a].push_back(b);
                g[b].push_back(a);
        }
        BiconnectedComponent bc(g);
        for (int i = 0; i < n; i ++) if (bc.ord[i] == -1) {
                bc.dfs(i, -1);
        }
        long long ans = 1;
        for (auto es : bc.bc) {
                if (es.size() == 1) {
                        ans = ans * k % MOD;
                        continue;
                }  
                map<int, int> z;
                int p = 0;
                for (auto e : es) {
                        if (!z.count(e.first)) z[e.first] = p ++;
                        if (!z.count(e.second)) z[e.second] = p ++;
                }
                vector<vector<int>> gg(p);
                for (auto e : es) {
                        gg[z[e.first]].push_back(z[e.second]);
                        gg[z[e.second]].push_back(z[e.first]);
                }
                bool cycle = true;
                for (int i = 0; i < p; i ++) {
                        cycle = cycle && ((int) gg[i].size() == 2);
                }
                if (cycle) {
                        int len = (int) es.size();
                        long long res = 0;
                        for (int i = 0; i < len; i ++) {
                                res = (res + ModPow(k, gcd(len, i), MOD)) % MOD;
                        }
                        ans = ans * res % MOD * Inv(len, MOD) % MOD;
                } else {
                        int len = (int) es.size();
                        ans = ans * C(len + k - 1, len) % MOD;
                }
        }
        printf("%lld\n", ans);
        return 0;
}



Measured memory_bytes: 117504