//by Sshwy
#include<algorithm>/*{{{*/
#include<cctype>
#include<cassert>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<vector>
using namespace std;
typedef pair<int,int> pii;
#define fi first
#define se second
#define pb push_back
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
namespace RA{
    int r(int p){return 1ll*rand()*rand()%p;}
    int r(int L,int R){return r(R-L+1)+L;}
}/*}}}*/
/******************heading******************/
const int N=500,P=1e9+7;
int pw(int a,int m){
    int res=1;
    while(m)m&1?res=1ll*res*a%P:0,a=1ll*a*a%P,m>>=1;
    return res;
}
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int n,m,k;

int dfn[N],low[N],totdfn;
int s[N],tp;
int totvcc;
vector<int> vcc[N],g[N];

void tarjan(int u,int p){
    dfn[u]=low[u]=++totdfn;
    s[++tp]=u;
    for(int v:g[u]){
        if(!dfn[v]){
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(dfn[u]<=low[v]){
                ++totvcc, vcc[totvcc].pb(u);
                do { vcc[totvcc].pb(s[tp]); }while(s[tp--]!=v);
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
}

int E[N][N],c[N][N];
int calc(int x,int k){
    int res=0;
    FOR(d,0,x-1){
        res=(res+pw(k,gcd(x,d)))%P;
    }
    res=1ll*res*pw(x,P-2)%P;
    return res;
}
int calc(vector<int> & A){
    if(A.size()==2)return k;//单独边
    int cnt=0;
    for(int i:A)for(int j:A)cnt+=E[i][j];
    assert(cnt%2==0);
    cnt/=2;
    if(cnt==A.size())return calc(cnt,k);
    return c[cnt+k-1][k-1];
}
int main(){
    scanf("%d%d%d",&n,&m,&k);

    c[0][0]=1;
    FOR(i,1,200){
        c[i][0]=1;
        FOR(j,1,i)c[i][j]=(c[i-1][j-1]+c[i-1][j])%P;
    }

    FOR(i,1,m){
        int u,v;
        scanf("%d%d",&u,&v);
        E[u][v]=E[v][u]=1;
        g[u].pb(v),g[v].pb(u);
    }
    FOR(i,1,n)if(!dfn[i])tarjan(i,0);

    int ans=1;
    FOR(i,1,totvcc){
        ans=ans*1ll*calc(vcc[i])%P;
    }

    printf("%d\n",ans);

    return 0;
}
