#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
constexpr lint MOD = 1000000007;


class UndirectedGraph
{
public:
    using Pint = pair<int, int>;

    int V; // 頂点数
    int E; // 辺の数
    int k;
    vector<vector<Pint>> to;
    vector<Pint> edges;

    vector<int> order, lowlink; // lowlink

    vector<vector<int> > bvc_edges;

public:
    UndirectedGraph(int V) : V(V), E(0), k(0),
                           to(vector<vector<Pint> >(V)), 
                           order(vector<int>(V, -1)),
                           lowlink(vector<int>(V, -1)) {}

    void add_edge(int v1, int v2)
    {
        to[v1].push_back(Pint(v2, E));
        to[v2].push_back(Pint(v1, E));
        edges.push_back(Pint(v1, v2));
        E++;
    }

    vector<Pint> edge_stack;
    void dfs_lowlink(int now, int prev = -1)
    {
        order[now] = lowlink[now] = k;
        k++;

        for (auto nxt : to[now]) if (nxt.first != prev)
        {
            if (order[nxt.first] < order[now]) edge_stack.push_back(nxt);
            if (order[nxt.first] < 0)
            {
                dfs_lowlink(nxt.first, now);
                lowlink[now] = min(lowlink[now], lowlink[nxt.first]);
                if (lowlink[nxt.first] >= order[now])
                {
                    bvc_edges.push_back(vector<int>());
                    while (1)
                    {
                        Pint edge = edge_stack.back();
                        int v1 = edges[edge.second].first;
                        int v2 = edges[edge.second].second;
                        edge_stack.pop_back();
                        bvc_edges.back().push_back(edge.second);
                        if (min(v1, v2) == min(now, nxt.first) && max(v1, v2) == max(now, nxt.first)) break;
                    }
                }
            } else lowlink[now] = min(lowlink[now], order[nxt.first]);
        }
    }
};

lint power(lint x, lint n)
{
    lint ans = 1;
    while (n>0)
    {
        if (n & 1) ans = ans * x % MOD;
        x = x * x % MOD;
        n >>= 1;
    }
    return ans;
}

vector<lint> factorial;
vector<lint> facInv;
void cPrecal(int n)
{
    factorial = facInv = vector<lint>(n+1, 1);
    for (int i=1; i<=n; i++)
    {
        factorial[i] = factorial[i-1] * i % MOD;
        facInv[i] = power(factorial[i], MOD-2);
    }
}

lint nCr(int n, int r)
{
    if (n<r || r<0) return 0;
    else return (factorial[n] * facInv[r] % MOD) * facInv[n-r] % MOD;
}

lint circle(int n, lint c)
{
    lint ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans += power(c, __gcd(i, n));
        ans %= MOD;
    }
    return ans * power(n, MOD-2) % MOD;
}

int N, M, K;
vector<int> a, b;

int main()
{
    cin >> N >> M >> K;
    cPrecal(N+M+K);

    UndirectedGraph graph(N);
    for (int i = 0; i < M; i++)
    {
        int v1, v2;
        cin >> v1 >> v2;
        graph.add_edge(v1 - 1, v2 - 1);
    }

    for (int i=0; i<N; i++) if(graph.order[i] < 0)
    {
        graph.dfs_lowlink(i);
    }

    lint ans = 1;
    for (int i = 0; i < graph.bvc_edges.size(); i++)
    {
        set<int> Vs;
        for (auto e : graph.bvc_edges[i])
        {
            Vs.insert(graph.edges[e].first);
            Vs.insert(graph.edges[e].second);
        }
        lint tmp;
        if (graph.bvc_edges[i].size() < Vs.size()) tmp = K;
        else if (graph.bvc_edges[i].size() > Vs.size()) tmp = nCr(graph.bvc_edges[i].size() + K - 1, K - 1);
        else tmp = circle(graph.bvc_edges[i].size(), K);
        ans = ans * tmp % MOD;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256