//by xxj
//I love 7 sea k fall
#include<bits/stdc++.h>
using namespace std;
#define fst first
#define snd second
#define mp make_pair
#define ll long long
#define pii pair<int,int>
#define lowbit(x) x&-x
const int inf=1e9+7;
const double eps=1e-10;
const ll linf=1e18+7;
const ll hh=523;
const int mod=1e9+7;
inline int read(){
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
int pow(int a,int c){
	int re=1;
	while (c){
		if (c&1){
			re=1ll*re*a%mod;
		}
		a=1ll*a*a%mod;
		c>>=1;
	}
	return re;
}
struct Edge{
	int next,to,bh;
}edge[207];
int head[207],len=0;;
void add(int x,int y,int bh){
	edge[len].next=head[x];
	edge[len].to=y;
	edge[len].bh=bh;
	head[x]=len++;
	edge[len].next=head[y];
	edge[len].to=x;
	edge[len].bh=bh;
	head[y]=len++;
}
ll ans=1;
int tot=1,cnt=0,num=0;
int js=0;
int dfn[57],low[57];
bool visited[207];
bool used[57];
int h1[107][107],dp[107][107],hn[107][107];
int jc[107],njc[107];
bool cut[107];
vector<int> hve[107];
bool f[107][107];
stack<int> st;
int n,m,k;
int rt;
int calc(int e,int c){
	int re=pow(c,e);
	for (int i=1;i<e;i++){
		re=(1ll*re+1ll*pow(c,__gcd(i,e)))%mod;
	}
	re=1ll*re*pow(e,mod-2)%mod;
	return re;
}
int C(int i,int j){
	return (1ll*jc[j]*njc[i]%mod)*njc[j-i]%mod;
}
void init(){
	jc[0]=1;
	for (int i=1;i<=k;i++){
		jc[i]=1ll*jc[i-1]*i%mod;
	}
	njc[k]=pow(jc[k],mod-2);
	for (int i=k-1;i>=0;i--){
		njc[i]=1ll*njc[i+1]*(i+1)%mod;
	}
	for (int i=1;i<=m;i++){
		for (int j=1;j<=k;j++){
			h1[i][j]=calc(i,j);
		}
	}
	for (int i=1;i<=k;i++){
		dp[1][i]=i;
	}
	for (int i=1;i<=m;i++){
		dp[i][1]=1;
	}
	for (int i=2;i<=m;i++){
		for (int j=2;j<=k;j++){
			for (int z=1;;z++){
				if (i-z<j-1){
					break;
				}
				dp[i][j]=(1ll*dp[i][j]+1ll*dp[i-z][j-1])%mod;
			}
		}
	}
	for (int i=1;i<=m;i++){
		for (int j=1;j<=k;j++){
			for (int z=1;z<=j;z++){
				hn[i][j]=(1ll*hn[i][j]+1ll*C(z,j)*dp[i][z]%mod)%mod;
			}
		}
	}
}
void tarjan(int v,int p){
	dfn[v]=tot;
	low[v]=tot++;
	st.push(v);
	int flag=0;
	for (int i=head[v];i!=-1;i=edge[i].next){
		int u=edge[i].to;
		if (!dfn[u]){
			tarjan(u,i);
			low[v]=min(low[v],low[u]);
			if (dfn[v]<=low[u]){
				flag++;
				if (v!=rt || flag>=2){
					cut[v]=true;
				}
				hve[js].push_back(v);
				f[js][v]=true;
				while (true){
					int z=st.top();
					st.pop();
					f[js][z]=true;
					hve[js].push_back(z);
					if (z==u){
						break;
					}
				}
				js++;
			}
		}
		else if (p==-1 || i!=(p^1)){
			low[v]=min(low[v],dfn[u]);
		}
	}
}
void dfs(int v,int c){
	used[v]=true;
	for (int i=head[v];i!=-1;i=edge[i].next){
		int u=edge[i].to;
		if (!f[c][u] || visited[i]){
			continue;
		}
		num++;
		visited[i]=true;
		visited[i^1]=true;
		if (used[u]){
			cnt++;
			continue;
		}
		dfs(u,c);
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	init();
	memset(head,-1,sizeof(head));
	for (int i=0;i<m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		x--;
		y--;
		add(x,y,i);
	}
	for (int i=0;i<n;i++){
		if (!dfn[i]){
			rt=i;
			tarjan(i,-1);
		}
	}
	for (int i=0;i<js;i++){
		memset(used,false,sizeof(used));
		cnt=0;
		num=0;
		dfs(hve[i][0],i);
		if (cnt==0){
			ans=1ll*ans*k%mod;
		} 
		else if (cnt==1){
			ans=1ll*ans*h1[num][k]%mod;
		}
		else{
			ans=1ll*ans*hn[num][k]%mod;
		}
	}
	printf("%lld\n",ans);
	return 0;
}
/*
input:
*/


Measured memory_bytes: 384