#include <bits/stdc++.h>
using namespace std;

const int NMAX = 51;
const int MMAX = 101;
const int KMAX = 101;

const int MOD = 1000000007;

pair<int, int> edg[MMAX]; bitset<NMAX> oki;
set<int> mst[MMAX]; vector<pair<int ,int>> gph[NMAX];

int cmb[MMAX + KMAX][MMAX + KMAX];
int lev[NMAX], anc[MMAX], fth[NMAX], fte[NMAX];

void dfs(int x, int f, int c, int &nr) {
    fth[x] = f; oki[x] = true;
    lev[x] = lev[f] + 1; fte[x] = c;
    
    for (pair<int, int> it : gph[x]) {
        int y, e;
        tie(y, e) = it;
        
        if (y == f)
            continue;
        
        if (!oki[y])
            dfs(y, x, e, nr);
        else
        if (lev[x] > lev[y]) {
            anc[++nr] = -1; mst[e].insert(nr);
            for (int p = x; p != y; p = fth[p])
                mst[fte[p]].insert(nr);
        }
    }
    
    return;
}

int getroot(int x) {
    if (anc[x] < 0)
        return x;
    else
        return getroot(anc[x]);
}

int lgput(int x, int n) {
    if (!n)
        return 1;
    
    int y = lgput(x, n >> 1);
    y = (1LL * y * y) % MOD;
    
    if (n & 1)
        y = (1LL * y * x) % MOD;
    
    return y;
}

int gcd(int x, int y) {
    while (y) {
        int z = x % y;
        x = y; y = z;
    }
    
    return x;
}

int main(void) {
    int n, m, k;
    cin >> n >> m >> k;
    
    for (int i = 1; i <= m; ++i) {
        int x, y;
        cin >> x >> y;
        
        edg[i] = make_pair(x, y);
        gph[x].push_back(make_pair(y, i));
        gph[y].push_back(make_pair(x, i));
    }
    
    int nr = 0, ans = 1;
    dfs(1, 0, 0, nr);
    
    for (int i = 0; i <= m + k - 1; ++i) {
        cmb[i][0] = 1;
        
        for (int j = 1; j <= i; ++j)
            cmb[i][j] = (cmb[i - 1][j - 1] + cmb[i - 1][j]) % MOD;
    }
    
    for (int i = 1; i <= m; ++i) {
        if (mst[i].empty())
            ans = (1LL * ans * k) % MOD;
        else {
            for (int x : mst[i]) {
                int r1 = getroot(*mst[i].begin()), r2 = getroot(x);
                
                if (r1 == r2)
                    continue;
                if (anc[r1] > anc[r2])
                    swap(r1, r2);
                
                anc[r1] += anc[r2];
                anc[r2] = r1;
            }
        }
    }
    
    for (int i = 1; i <= nr; ++i) {
        if (anc[i] > 0)
            continue;
        
        int val = 0;
        for (int j = 1; j <= m; ++j)
            if (mst[j].size())
                val += (getroot(*mst[j].begin()) == i);
        
        if (anc[i] < -1)
            ans = (1LL * ans * cmb[val + k - 1][k - 1]) % MOD;
        else {
            int aux = 0;
            for (int j = 1; j <= val; ++j)
                aux = (aux + lgput(k, gcd(val, j))) % MOD;
            
            aux = (1LL * aux * lgput(val, MOD - 2)) % MOD;
            ans = (1LL * ans * aux) % MOD;
        }
    }
    
    cout << ans << endl;
    return 0;
}