#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=110,p=1e9+7;
int inc(int x,int y){x+=y;return x>=p?x-p:x;}
int dec(int x,int y){x-=y;return x<0?x+p:x;}
int mul(int x,int y){return (ll)x*y%p;}
int power(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=mul(x,x))
		if (y&1) ans=mul(ans,x);
	return ans;
}
int n,m,k,dfn[N],low[N],fac[N],ifac[N];
vector<int> e[N];
typedef pair<int,int> pii;
pii sta[N];int top,ans=1;
int gcd(int x,int y){return y?gcd(y,x%y):x;}
int dp[N][N][N];
//dp[i][j][k]表示把i拆成j项之和，最大的是k的方案数
int calc_partition(int n){//拆分数列
	int ans=0;
	for (int i=1;i<=n&&i<=k;i++)
		ans=inc(ans,mul(dp[n][i][n+1],ifac[k-i]));
	return mul(ans,fac[k]);
}
int calc_cir(int n){
	int ans=0;
	for (int i=1;i<=n;i++) ans=inc(ans,power(k,gcd(i,n)));
	return mul(ans,power(n,p-2));
}
int calc(int l,int r){
	//for (int i=l;i<=r;i++) printf("%d %d\n",sta[i].first,sta[i].second);puts("");
	if (l==r) return k;
	static int vis[N],C;C++;
	int v=0,e=r-l+1;
	for (int i=l;i<=r;i++){
		int x=sta[i].first,y=sta[i].second;
		if (vis[x]!=C) vis[x]=C,v++;
		if (vis[y]!=C) vis[y]=C,v++;
	}
	if (v==e) return calc_cir(e);
	else return calc_partition(e);
}
void tarjan(int x,int fa){
	static int cnt=0;
	dfn[x]=low[x]=++cnt;
	for (int i=0;i<e[x].size();i++){
		int v=e[x][i];
		if (v==fa) continue;
		if (dfn[v]){
			low[x]=min(low[x],dfn[v]);
			if (dfn[x]>dfn[v]) sta[++top]=pii(x,v);
		}
		else{
			sta[++top]=pii(x,v);
			int last=top;
			tarjan(v,x);
			low[x]=min(low[x],low[v]);
			//x是割点,栈内的边就是个bcc
			if (low[v]>=dfn[x]) ans=mul(ans,calc(last,top)),top=last-1;
		}
	}
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	fac[0]=1;
	for (int i=1;i<N;i++) fac[i]=mul(fac[i-1],i);
	ifac[N-1]=power(fac[N-1],p-2);
	for (int i=N-1;i;i--) ifac[i-1]=mul(ifac[i],i);
	dp[0][0][1]=1;
	for (int i=0;i<=100;i++)
	for (int j=0;j<=i;j++)
	for (int k=1;k<=100;k++)
	for (int a=0;i+k*a<=100;a++){
		int &to=dp[i+k*a][j+a][k+1];
		to=inc(to,mul(dp[i][j][k],ifac[a]));
	}
	for (int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	for (int i=1;i<=n;i++)
		if (!dfn[i]) tarjan(i,0);
	printf("%d\n",ans);
	return 0;
}