#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e5+10;
const int mod=1e9+7;
int n,m,k,c[N],u[N],v[N],ans;
int f[N],g[N];
void calc(){
	for(int i=1;i<=m;i++){
		if(c[u[i]]==c[v[i]])return;
	}	
	ans++;
	return;
}
void dfs(int x){
	if(x==n+1){
		calc();
	}else{
		for(int i=1;i<=k;i++){
			c[x]=i;
			dfs(x+1);
			c[x]=0;
		}
	}
	return;
}
int main(){
	freopen("color.in","r",stdin);
	freopen("color.out","w",stdout);
	scanf("%d %d %d",&n,&m,&k);
	for(int i=1;i<=m;i++){
		scanf("%d %d",u+i,v+i);
	}
	if(n<=10){
		dfs(1);
		printf("%d\n",ans);
	}else{
		f[1]=k,g[3]=1ll*k*(k-1)%mod;
		for(int i=2;i<=n;i++){
			f[i]=1ll*f[i-1]*(k-1)%mod;
		}
		for(int i=4;i<=n;i++){
			g[i]=f[i-1]-g[i-1]; 
			g[i]=(g[i]%mod+mod)%mod;
		}
		if(m==n-1)printf("%d\n",f[n]);
		else printf("%d\n",(f[n]-g[n]+mod)%mod);
	}
	return 0;
}