#include<cstdio>
#include<algorithm>
using namespace std;
const int Mod=1e9+7;
typedef long long ll;
int n,m,k,u,v,cnt,bcc[410],dfn[410],low[410],C[1100][1100],dt,ans;
int st[410],top;
bool vis[410];
int edgenum=1,vet[410],Next[410],Head[110];
int gcd(int a,int b){ return a%b==0?b:gcd(b,a%b);}
void addedge(int u,int v){
    vet[++edgenum]=v;
    Next[edgenum]=Head[u];
	Head[u]=edgenum;
}
int qpow(int x,int a){
    int res=1;
    while (a){
        if (a&1) res=(ll)res*x%Mod;
        x=(ll)x*x%Mod; a>>=1;
    }
    return res;
}
int polya(int n){
	int ret=0;
	for (int i=1;i<=n;i++) ret=(ret+qpow(k,gcd(i,n)))%Mod;
	return (ll)ret*qpow(n,Mod-2)%Mod;
}
void tarjan(int u){
	dfn[u]=low[u]=++dt;
	st[++top]=u;
	int v;
	for(int e=Head[u];e;e=Next[e]){
		v=vet[e];
		if (!dfn[v]){
			tarjan(v);
			if (low[v]>=dfn[u]){
                cnt=0; 
                do{ bcc[++cnt]=st[top];} while (st[top--]!=v);
                bcc[++cnt]=u;
                for (int i=1;i<=cnt;i++) vis[bcc[i]]=true;
                int m=0;
                for (int i=1;i<=cnt;i++)
                	for (int j=Head[bcc[i]];j;j=Next[j])
                		if (vis[vet[j]]) m++;
                m>>=1;
                if (m<cnt) ans=(ll)ans*k%Mod;
                if (m==cnt) ans=(ll)ans*polya(cnt)%Mod;
                if (m>cnt) ans=(ll)ans*C[m+k-1][k-1]%Mod;
                for (int i=1;i<=cnt;i++) vis[bcc[i]]=false;
			}
            low[u]=min(low[u],low[v]);
		} else low[u]=min(low[u],dfn[v]);
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for (int i=1;i<=m;i++){
		scanf("%d%d",&u,&v);
		addedge(u,v); addedge(v,u);
	}
	C[0][0]=1;
	for (int i=1;i<=1000;i++){
		C[i][0]=1;
		for (int j=1;j<=i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%Mod;
	}
    ans=1;
    for (int i=1;i<=n;i++)
        if (!dfn[i]) tarjan(i);
    printf("%d\n",ans);
	return 0;
}
