#include<stdio.h>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;
const int mod=1000000007;
int mul(int a,int b){return a*(ll)b%mod;}
void inc(int&a,int b){(a+=b)%=mod;}
int pow(int a,int b){
    int s=1;
    while(b){
        if(b&1)s=mul(s,a);
        a=mul(a,a);
        b>>=1;
    }
    return s;
}
vector<int>g[60];
int fac[210],rfac[210],k;
int C(int n,int k){return mul(fac[n],mul(rfac[k],rfac[n-k]));}
int dfn[60],low[60],stk[60],tp,M,ans;
set<int>s;
int gcd(int a,int b){return a%b==0?b:gcd(b,a%b);}
int burnside(int n){
    int i,s=0;
    for(i=1;i<=n;i++)inc(s,pow(k,gcd(i,n)));
    return mul(s,pow(n,mod-2));
}
void dfs(int x){
    int t,n,m;
    dfn[x]=low[x]=++M;
    stk[++tp]=x;
    for(int y:g[x]){
        if(!dfn[y]){
            dfs(y);
            low[x]=min(low[x],low[y]);
            if(low[y]>=dfn[x]){
                s.clear();
                do{
                    t=stk[tp--];
                    s.insert(t);
                }while(t!=y);
                s.insert(x);
                n=s.size();
                m=0;
                for(int x:s){
                    for(int y:g[x]){
                        if(s.count(y))m++;
                    }
                }
                m>>=1;
                if(m<n)ans=mul(ans,k);
                if(n==m)ans=mul(ans,burnside(m));
                if(n<m)ans=mul(ans,C(m+k-1,k-1));
            }
        }else
            low[x]=min(low[x],dfn[y]);
    }
}
int main(){
    int n,m,i,x,y;
    scanf("%d%d%d",&n,&m,&k);
    for(i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    fac[0]=1;
    for(i=1;i<=m+k;i++)fac[i]=mul(fac[i-1],i);
    rfac[m+k]=pow(fac[m+k],mod-2);
    for(i=m+k;i>0;i--)rfac[i-1]=mul(rfac[i],i);
    ans=1;
    for(i=1;i<=n;i++){
        if(!dfn[i])dfs(i);
    }
    printf("%d",ans);
}