#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N=210,M=1000010,P=1e9+7;
const int inf=0x3f3f3f3f;
const int INF=0xcfcfcfcf;
const double eps=1e-9,pi=asin(1)*2;
inline ll read();
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
inline int ADD(int a,int b) { return a+b>=P?a+b-P:a+b; }
inline int MINUS(int a,int b) { return a-b<0?a-b+P:a-b; }
#define plus(a,b) a=ADD(a,b)
#define minus(a,b) a=MINUS(a,b)
#define mul(a,b) a=(1ll*a*(b))%P
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define mp(x,y) make_pair(x,y)

inline int gcd(int x,int y) { return y?gcd(y,x%y):x; }
inline int quickmi(int x,int n)
{
	int res=1;
	for(;n;n>>=1)
	{
		if(n&1) mul(res,x);
		mul(x,x);
	}
	return res;
}
#define ni(x) quickmi(x,P-2)

int head[N],ver[M],nxt[M];
int n,m,k,tot=1;
inline void add(int x,int y)
{
	ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;
}

int C[N][N];
inline void init(int n=200)
{
	for(int i=0;i<=n;i++)
	{
		C[i][0]=1;
		for(int j=1;j<=n;j++) C[i][j]=ADD(C[i-1][j-1],C[i-1][j]);
	}
}

int ans=1;
int dfn[N],low[N],visit[N];
//vector<int> dcc[N];
int sta[N],top=0,num=0,cnt=0;
bool ins[N];
inline void tarjan(int x,int fa)
{
	dfn[x]=low[x]=++num;
	ins[sta[++top]=x]=true;
	for(int i=head[x];i;i=nxt[i])
	{
		int y=ver[i];
		if(y==fa) continue;
		if(!dfn[y])
		{
			tarjan(y,x);
			cmin(low[x],low[y]);
			if(low[y]>=dfn[x])
			{
				int z=0,s1=1,s2=0;
//				cnt++;
				visit[x]=++cnt;
//				while(z!=y) ins[z=sta[top--]]=false,dcc[cnt].push_back(z),visit[z]=true;
				while(z!=y)
				{
					ins[z=sta[top--]]=false;
					for(int j=head[z];j;j=nxt[j])
					{
						int yy=ver[j];
						if(visit[yy]==cnt) s2++;
					}
					visit[z]=cnt,s1++;
				}
//				dcc[cnt].push_back(x),visit[x]=true;
				if(s2<s1) mul(ans,k);
				if(s2==s1)
				{
					int tmp=0;
					for(int d=0;d<s2;d++) plus(tmp,quickmi(k,gcd(d,s2)));
					mul(tmp,ni(s2));
					mul(ans,tmp);
				}
				if(s2>s1) mul(ans,C[s2+k-1][k-1]);
			} 
		}
		else if(ins[y]) cmin(low[x],dfn[y]);
	}
}

//#define FILE "F"
#ifdef FILE
const int RS=1<<20;
char buf[RS],*p1=buf,*p2=buf;
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,RS,stdin),p1==p2)?EOF:*p1++
#endif
inline ll read()
{
	ll s=0;
	bool flag=false;
	char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') flag=true;
	for(;'0'<=ch&&ch<='9';ch=getchar()) s=(s<<3)+(s<<1)+(ch^'0');
	if(flag) return -s;
	return s;
}

int main()
{
#ifdef FILE
	freopen(FILE ".in","r",stdin);
	freopen(FILE ".out","w",stdout);
#endif
	init();
	n=read(),m=read(),k=read();
	for(int i=1;i<=m;i++)
	{
		int x=read(),y=read();
		add(x,y),add(y,x);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i]) tarjan(i,0);
/*
	int ans=1,res=m;
	for(int i=1;i<=cnt;i++)
	{
		int sz=dcc[i].size(),s2=0;
		for(int j=0;j<sz;j++) visit[dcc[i][j]]=true;
		
		for(int j=0;j<sz;j++)
		{
			int x=dcc[i][j];
			for(int l=head[x];l;l=nxt[l])
			{
				int y=ver[l];
				if(x>y||!visit[y]) continue;
				s2++;
			}
		}
		if(s2>=sz)
		{
			if(s2==sz)
			{
				int tmp=0;
				for(int d=0;d<s2;d++) plus(tmp,quickmi(k,gcd(d,s2)));
				mul(tmp,ni(s2));
//				cerr<<tmp<<"\n";
				mul(ans,tmp);
			}
			else mul(ans,C[s2+k-1][k-1]);
			res-=s2;
		}
		
		for(int j=0;j<sz;j++) visit[dcc[i][j]]=false;
	}
	mul(ans,quickmi(k,res));
//*/
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 2432