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

typedef long long LL;
const int MAXN=300+10;
const int mod=1e9+7;
const double EPS=1e-8;

int n,m,t,cnt;

vector<int> edge[MAXN];
int dfn[MAXN],low[MAXN],vis[MAXN],used[MAXN][MAXN];
stack<pair<int,int> >s;

LL fra[MAXN],inv[MAXN],bur[MAXN],ans;

LL gcd(LL a,LL b){
    if (b==0) return a;
    else return gcd(b,a%b);
}

LL power(LL a,LL b){
    LL c=1;
    while(b){
        if (b%2==1) c=c*a%mod;
        a=a*a%mod;
        b/=2;
    }
    return c;
}

LL C(LL a,LL b){
    if (a<0 || b<0 || a<b) return 0;
    return (fra[a]*inv[b]%mod)*inv[a-b]%mod;
}

LL Burnside(LL len,LL col){
    if (bur[len]!=0) return bur[len];
    LL sum=0;
    for(int i=1;i<=len;i++){        
        sum+=power(col,gcd(i,len));
        if (sum>=mod) sum-=mod;
    }
    sum*=power(len,mod-2);
    sum%=mod;
    return sum;
}

void dfs(int u,int fa){
    dfn[u]=low[u]=++cnt;
    for(int i=0;i<edge[u].size();i++){
        int v=edge[u][i];
        if (used[u][v]!=0) continue;
        s.push(make_pair(min(u,v),max(u,v)));
        used[u][v]=used[v][u]=1;
        if (dfn[v]==0){
            dfs(v,u);
            low[u]=min(low[u],low[v]);
            if (low[v]>=dfn[u]){
                int nume=0,numv=0;
                while(1){
                    pair<int,int> e=s.top(); s.pop();
                    nume++;
                    //cout<<e.first<<' '<<e.second<<endl;
                    if (vis[e.first]!=cnt) numv++,vis[e.first]=cnt;
                    if (vis[e.second]!=cnt) numv++,vis[e.second]=cnt;
                    if (e.first==min(u,v) && e.second==max(u,v)) break;
                }
                //cout<<endl;
                cnt++;
                if (numv==nume+1) ans=ans*t%mod;
                else{
                    if (numv==nume) ans=ans*Burnside(numv,t)%mod;
                    else ans=ans*C(nume+t-1,t-1)%mod;
                }
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
}

int main(){
    scanf("%d%d%d",&n,&m,&t);
    fra[0]=1; for(int i=1;i<=m+t;i++) fra[i]=fra[i-1]*i%mod;
    inv[m+t]=power(fra[m+t],mod-2); for(int i=m+t-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
    memset(bur,0,sizeof(bur));
    
    for(int i=1;i<=m;i++){
        int a,b; scanf("%d%d",&a,&b);
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(vis,0,sizeof(vis));
    memset(used,0,sizeof(used));
    cnt=0; ans=1;
    for(int i=1;i<=n;i++)
        if (dfn[i]==0) dfs(i,0);
    printf("%lld\n",ans);
    return 0;
}