#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;

struct edge {
        int to, idx;
};

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 UnionFind {
        int n;
        vector<int> parent;
        vector<int> rank;
        vector<int> num;
        int find(int x) {
                if (parent[x] == x) return  x;
                return parent[x] = find(parent[x]);
        }
        UnionFind(int n_) {
                n = n_;
                parent.resize(n);
                for (int i = 0; i < n; i ++) parent[i] = i;
                rank.assign(n, 0);
                num.assign(n, 1);
        }
        void unite(int x, int y) {
                if ((x = find(x)) != (y = find(y))) {
                        if (rank[x] < rank[y]) {
                                parent[x] = y;
                                num[y] += num[x];
                        } else {
                                parent[y] = x;
                                if (rank[x] == rank[y]) rank[x] ++;
                                num[x] += num[y];
                        }
                        n --;
                }
        }
        bool same(int x, int y) { return find(x) == find(y); }
        int get() { return n; }
        int get(int x) { return num[find(x)]; }
};

int main() {
        init();
        int n, m, k;
        scanf("%d%d%d", &n, &m, &k);
        vector<vector<edge>> g(n);
        vector<pair<int, int>> edges(m);
        for (int i = 0; i < m; i ++) {
                int a, b;
                scanf("%d%d", &a, &b);
                a --, b --;
                g[a].push_back({b, i});
                g[b].push_back({a, i});
                edges[i] = {a, b};
        }
        vector<int> color(m, -1);
        UnionFind uf(m);
        int root;
        function<void (int, int)> dfs = [&](int u, int c) {
                for (auto e : g[u]) if (color[e.idx] == -1) {
                        color[e.idx] = c;
                        if (e.to != root) {
                                dfs(e.to, c);
                        }
                }
        };
        for (int u = 0; u < n; u ++) {
                color.assign(m, -1);
                int c = 0;
                root = u;
                for (auto e : g[u]) if (color[e.idx] == -1) {
                        color[e.idx] = c;
                        dfs(e.to, c);
                        c ++;
                }                  
                for (auto e1 : g[u]) {
                        for (auto e2 : g[u]) {
                                if (color[e1.idx] == color[e2.idx] && !uf.same(e1.idx, e2.idx)) {
                                        uf.unite(e1.idx, e2.idx);
                                }
                        }
                }
        }
        map<int, vector<pair<int, int>>> bc; // parent index, edge set
        for (int i = 0; i < m; i ++) {
                int par = uf.find(i);
                bc[par].push_back(edges[i]);
        }
        long long ans = 1;
        for (auto comp : bc) {
                if (comp.second.size() == 1) {
                        ans = ans * k % MOD;
                        continue;
                }  
                map<int, int> z;
                int p = 0;
                for (auto e : comp.second) {
                        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 : comp.second) {
                        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) comp.second.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) comp.second.size();
                        ans = ans * C(len + k - 1, k - 1) % MOD;
                }
        }
        printf("%lld\n", ans);
        return 0;
}


Measured memory_bytes: 117504