#include<bits/stdc++.h>
using namespace std;
const int N = 55;
const int MM = 111;
const int mod = 1e9 + 7;
#define P pair<int, int>
#define mk_p make_pair
#define fs first
#define sc second
int head[N], nex[MM<<1], to[MM<<1], size = 1;
int n, m, K;
int col[N], dfn[N], low[N], cnt, tot, tp;
int sz_e[N], sz_v[N];
P zh[MM<<1];
int C[222][222];
inline int A(int x, int y){
    return x + y - (x + y >= mod ? mod : 0);
}
inline int M(int x, int y){
    return 1LL * y * x % mod;
}
int gcd(int x, int y){
    return !y ? x : gcd(y, x % y);
}
void add(int x, int y){
    to[++size] = y;
    nex[size] = head[x];
    head[x] = size;
}
int ksm(int base, int x){
    int ans = 1;
    while(x){
        if(x & 1)ans = M(ans, base);
        base = M(base, base);
        x >>= 1;
    }
    return ans;
}
void tarjan(int u, int lst){
    dfn[u] = low[u] = ++cnt;
    for(int i = head[u];i;i = nex[i]){
        if(i == lst)continue;
        int v = to[i];
		if(dfn[v] > dfn[u])continue;
        zh[++tp] = mk_p(u, v);
        if(!dfn[v]){
            tarjan(v, i ^ 1);
            low[u] = min(low[v], low[u]);
            if(low[v] >= dfn[u]){
                tot++;
				int x, y;
                do{
                    x = zh[tp].fs, y = zh[tp].sc;
                    sz_e[tot]++;
                    if(col[x] != tot)col[x] = tot, sz_v[tot]++;
                    if(col[y] != tot)col[y] = tot, sz_v[tot]++;
                    tp--;
                }while(x != u || y != v);
            }
        }
        else low[u] = min(low[u], dfn[v]);
    }
}
int main(){
    C[0][0] = 1;
    for(int i = 1;i <= 202; i++){
        C[i][0] = 1;
        for(int j = 1;j <= i; j++)C[i][j] = A(C[i-1][j], C[i-1][j-1]);
    }   
    cin>>n>>m>>K;
    int u, v;
    for(int i = 1;i <= m; i++){
        cin>>u>>v;
        add(u, v); add(v, u);
    }
    for(int i = 1;i <= n; i++){
        if(!dfn[i])tarjan(i, 0);
    }
    int ans = 1;
    for(int i = 1;i <= tot; i++){
        if(sz_e[i] == 1){
            ans = M(ans, K);
        }
        else if(sz_e[i] == sz_v[i]){
            int sum = 0;
            for(int j = 1;j <= sz_e[i]; j++){
                sum = A(sum, ksm(K, gcd(j, sz_e[i])));
            }
            sum = M(sum, ksm(sz_e[i], mod - 2));
            ans = M(ans, sum);
        }
        else ans = M(ans, C[K+sz_e[i]-1][K-1]);
    }
    cout<<ans<<endl;
    return 0;
}