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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

const int mod=1000000007;
int mpow(int n,int m){
    int ret=1;
    while(m){
        if(m&1)ret=ret*n%mod;
        n=n*n%mod;
        m>>=1;
    }
    return ret;
}
const int FACT_SIZE=1111111;
int fact[FACT_SIZE];
int inv[FACT_SIZE];
struct fact_exec{
    fact_exec(){
        fact[0]=1;
        for(int i=1;i<FACT_SIZE;i++)fact[i]=fact[i-1]*i%mod;
        inv[FACT_SIZE-1]=mpow(fact[FACT_SIZE-1],mod-2);
        for(int i=FACT_SIZE-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
    }
}factexec;
int nCk(int n,int k){
    return fact[n]*inv[k]%mod*inv[n-k]%mod;
}
int nPk(int n,int k){
    return fact[n]*inv[n-k]%mod;
}

struct UnionFindTree{
    vector<int>par,sz;
    UnionFindTree(int n){
        par.resize(n);
        sz.resize(n);
        for(int i=0;i<n;i++){
            par[i]=i;
            sz[i]=1;
        }
    }
    int find(int x){
        return x==par[x]?x:par[x]=find(par[x]);
    }
    void unite(int x,int y){
        x=find(x);y=find(y);
        if(x==y)return;
        if(sz[x]<sz[y])swap(x,y);
        sz[x]+=sz[y];
        par[y]=x;
    }
    bool areSame(int x,int y){
        return find(x)==find(y);
    }
    int size(int x){
        return sz[find(x)];
    }
};

int N,M,K;
int A[111],B[111];
int dp[111];

int ei(int n){
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++){
        if(n%i)continue;
        dp[i]=mpow(K,i);
        for(int j=1;j<i;j++)if(i%j==0)dp[i]=(dp[i]-dp[j]+mod)%mod;
    }
    int ret=0;
    for(int i=1;i<=n;i++)ret=(ret+dp[i]*mpow(i,mod-2))%mod;
    return ret;
}

struct BiconnectedComponent{
    int N;
    vector<vector<int>>G;
    vector<vector<pair<int,int>>>bc;
    vector<int>ord,low,used;
    stack<pair<int,int>>stk;

    BiconnectedComponent(const vector<vector<int>>&G):G(G){
        N=G.size();
        ord=vector<int>(N);
        low=vector<int>(N);
        used=vector<int>(N);
        int k=0;
        for(int i=0;i<N;i++){
            if(used[i])continue;
            dfs(i,-1,k);
        }
    }

    void dfs(int v,int p,int &k){
        ord[v]=k++;
        low[v]=ord[v];
        used[v]=true;

        for(auto u:G[v]){
            if(u==p)continue;
            if(ord[u]<=ord[v])stk.push({min(u,v),max(u,v)});
            if(!used[u]){
                dfs(u,v,k);
                low[v]=min(low[v],low[u]);
                if(ord[v]<=low[u]){
                    bc.push_back({});
                    while(true){
                        pair<int,int>e=stk.top();
                        stk.pop();
                        bc.back().push_back(e);
                        if(e.first==min(u,v)&&e.second==max(u,v))break;
                    }
                }
            }
            else{
                low[v]=min(low[v],ord[u]);
            }
        }
    }
};

signed main(){
    cin>>N>>M>>K;
    rep(i,M)cin>>A[i]>>B[i],A[i]--,B[i]--;

    vector<vector<int>>G(N);
    rep(i,M)G[A[i]].pb(B[i]),G[B[i]].pb(A[i]);

    BiconnectedComponent bc(G);
    int ans=1;
    for(auto &es:bc.bc){
        set<int>vs;
        for(auto &e:es)vs.insert(e.first),vs.insert(e.second);

        if(es.size()==1){
            ans=ans*K%mod;
        }
        else if(es.size()==vs.size()){
            ans=ans*ei(es.size())%mod;
        }
        else{
            ans=ans*nCk(es.size()+K-1,K-1)%mod;
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 17664