#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define rep(i,a,b) for(int i=(a),i##_end_=(b);i<=i##_end_;i++)
#define dwn(i,a,b) for(int i=(a),i##_end_=(b);i>=i##_end_;i--)
using namespace std;
inline int read() {
    int x=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=210;
const int mod=1000000007;
int n,m,k,first[maxn],nxt[maxn],to[maxn],e;
void AddEdge(int u,int v) {
	to[e]=v;nxt[e]=first[u];first[u]=e++;
	to[e]=u;nxt[e]=first[v];first[v]=e++;
}
int findset(int x,int* pa) {return x==pa[x]?x:pa[x]=findset(pa[x],pa);}
int pa[maxn],tree[maxn],cnt,sum[maxn],yes[maxn];
int vis[maxn],fa[maxn],dep[maxn],clo;
void merge(int x,int y) {
	sum[y]+=sum[x];yes[y]+=yes[x];
	pa[x]=y;
}
void dfs(int x,int la) {
	vis[x]=++clo;dep[x]=dep[fa[x]]+1;
	for(int i=first[x];~i;i=nxt[i]) if(i!=(la^1)) {
		if(!vis[to[i]]) fa[to[i]]=x,dfs(to[i],i);
		else if(vis[to[i]]<vis[x]) {
			int j=findset(x,tree);
			while(dep[j]>dep[to[i]]+1) {
				tree[j]=fa[j];
				merge(findset(j,pa),findset(fa[j],pa));
				j=findset(j,tree);
			}
			cnt++;pa[cnt]=cnt;sum[cnt]=yes[cnt]=1;
			merge(findset(j,pa),cnt);
		}
	}
}
int pw[maxn],inv[maxn],fac[maxn],ifac[maxn];
int S[maxn][maxn];
int gcd(int a,int b) {return !b?a:gcd(b,a%b);}
int C(int a,int b) {return (ll)fac[a]*ifac[b]%mod*ifac[a-b]%mod;}
void init() {
	pw[0]=inv[1]=fac[0]=ifac[0]=1;
	rep(i,1,m) pw[i]=(ll)pw[i-1]*k%mod;
	rep(i,2,m+k) inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
	rep(i,1,m+k) fac[i]=(ll)fac[i-1]*i%mod,ifac[i]=(ll)ifac[i-1]*inv[i]%mod;
}
int main() {
	memset(first,-1,sizeof(first));
	n=read();m=read();k=read();
	rep(i,1,m) AddEdge(read(),read());
	init();
	rep(i,1,n) pa[i]=i,tree[i]=i,sum[i]=1;
	cnt=n;
	rep(i,1,n) if(!vis[i]) dfs(i,-1);
	int circle=0,complex=0,ans=1;
	rep(i,n+1,cnt) if(findset(i,pa)==i) {
		if(yes[i]!=1) {
			complex+=sum[i];
			ans=(ll)ans*C(sum[i]+k-1,k-1)%mod;
		}
		else {
			circle+=sum[i];
			int res=0;
			rep(j,0,sum[i]-1) (res+=pw[gcd(sum[i],j)])%=mod;
			res=(ll)res*inv[sum[i]]%mod;
			ans=(ll)ans*res%mod;
		}
	}
	rep(i,1,m-circle-complex) ans=(ll)ans*k%mod;
	printf("%d\n",ans);
	return 0;
}