#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,P=1e9+7;
int n,m,c,f[N][3],pw[N],ans=1,id[N];
int dp[1<<16],g[1<<16],h[1<<16],va[21],lb[1<<16];
multiset<pair<int,int> >e[N];
bool vis[N];
queue<int>q;
vector<int>vc;
inline void Add(int &x,int y){
	if((x+=y)>=P)x-=P;
}
void init(){
	f[0][1]=f[0][2]=pw[0]=1;
	for(int i=1;i<=n;++i){
		f[i][0]=pw[i]=1ll*(c-1)*pw[i-1]%P;
		f[i][1]=f[i-1][0];
		Add(f[i][0],P-f[i][1]);
		f[i][2]=(1ll*f[i-1][2]*(c-2)+f[i][1])%P;
	}
	for(int i=1;i<=n;++i)if(e[i].size()<3)vis[i]=true,q.push(i);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		if(e[u].empty()){
			ans=1ll*c*ans%P;
			printf("%d\n",ans);
			exit(0);
		}
		if(e[u].size()==1){
			auto [x,y]=*e[u].begin();
			ans=1ll*ans*pw[y]%P;
			e[x].erase(e[x].find({u,y}));
			if(e[x].size()<3&&!vis[x])q.push(x),vis[x]=true;
		}else{
			auto [x1,y1]=*e[u].begin();
			auto [x2,y2]=*e[u].rbegin();
			e[x1].erase(e[x1].find({u,y1}));
			e[x2].erase(e[x2].find({u,y2}));
			if(x1==x2)ans=1ll*ans*f[y1+y2][1]%P;
			else{
				e[x1].emplace(x2,y1+y2);
				e[x2].emplace(x1,y1+y2);
			}
		}
	}
}
void DP(){
	for(int i=1;i<=n;++i)if(!vis[i])id[i]=vc.size(),vc.emplace_back(i);
	m=vc.size();
	for(int S=1;S<1<<m;++S){
		for(int j=m-1;~j;--j)if(S>>j&1)lb[S]=j;
		h[S]=1;
		for(int j=0;j<m;++j)if(S>>j&1)
			for(auto [x,y]:e[vc[j]])if(id[x]>j&&(S>>id[x]&1))h[S]=1ll*h[S]*f[y][1]%P;
	}
	dp[0]=g[0]=1;
	int res=0;
	for(int i=1,fac=1;i<=m;++i){
		for(int S=(1<<m)-1;~S;--S)if(dp[S]){
			int U=(1<<m)-1^S;
			for(int j=0;j<m;++j)if(U>>j&1){
				va[j]=1;
				for(auto [x,y]:e[vc[j]])if(S>>id[x]&1)va[j]=1ll*va[j]*f[y-1][2]%P;
			}
			for(int T=U,W;;T=(T-1)&U){
				W=U^T;
				if(W)g[W]=1ll*g[W^(1<<lb[W])]*va[lb[W]]%P;
				if(!(T>>lb[U]&1))Add(dp[S|W],1ll*g[W]*h[W]%P*dp[S]%P);
				if(!T)break;
			}
			dp[S]=0;
		}
		fac=1ll*fac*(c-i+1)%P;
		Add(res,1ll*fac*dp[(1<<m)-1]%P);
	}
	printf("%d\n",1ll*ans*res%P);
}
int main(){
	scanf("%d%d%d",&n,&m,&c);
	for(int i=1,x,y;i<=m;++i){
		scanf("%d%d",&x,&y);
		if(e[x].find({y,1})!=e[x].end())continue;
		e[x].emplace(y,1);
		e[y].emplace(x,1);
	}
	init();
	DP();
	return 0;
}