#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=220;
const int mod=1000000007;
int n,m,k,X[N],Y[N],F[N],c[N][N],dfn[N],low[N],inq[N],S[N],fla[N],tot=1,top; long long ans=1;
vector<int>V[N];
void dfs(int x,int f){
    dfn[x]=low[x]=tot++,inq[x]=1,S[++top]=x;
    for(int t,i=0;i<V[x].size();i++){
        t=V[x][i]; if(t==f)continue;
        if(!dfn[t]){
            dfs(t,x),low[x]=min(low[t],low[x]);
            if(low[t]>=dfn[x]){
                int edg=0,cnt=0;
                do{fla[S[top]]=1,inq[S[top]]=0;}while(S[top--]!=t); fla[x]=1;
                for(int i=1;i<=m;i++) if(fla[X[i]]&&fla[Y[i]]) ++edg;
                for(int i=1;i<=n;i++) if(fla[i]) ++cnt,fla[i]=0;
                if(edg==cnt-1)(ans*=k)%=mod;
                else if(edg==cnt)(ans*=F[edg])%=mod;
                else (ans*=c[edg+k-1][k-1])%=mod;
            }
        }
        else if(inq[x])low[x]=min(low[x],dfn[t]);
    }
}
int gcd(int x,int y){return y?gcd(y,x%y):x;}
int qpw(int x,int n){
    int ret=1; for(;n;n>>=1,x=1ll*x*x%mod)
    if(n&1) ret=1ll*ret*x%mod; return ret;
}
int main(){
    scanf("%d%d%d",&n,&m,&k),c[0][0]=1;
    for(int i=1;i<=m;i++)scanf("%d%d",X+i,Y+i),V[X[i]].pb(Y[i]),V[Y[i]].pb(X[i]);
    for(int i=1;i<=m+k;i++) for(int j=0;j<=m+k;j++) c[i][j]=(c[i-1][j]+(j?c[i-1][j-1]:0))%mod;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++)(F[i]+=qpw(k,gcd(i,j)))%=mod;
        F[i]=1ll*F[i]*qpw(i,mod-2)%mod;
    }
    for(int i=1;i<=n;i++)if(!dfn[i])dfs(i,0);
    printf("%lld\n",ans);
}
