#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
using namespace std;
const int MAXN=55;
const int MAXM=110;
const int P=1E9+7;
struct Edge
{
	int from, to;
	Edge(int u, int v): from(u), to(v) {}
};
int n, m, k, cnt, t1, t2, tot;
int c[2*MAXM][MAXM], f[MAXM];
int dfn[MAXN], low[MAXN];
int s1[MAXN], s2[MAXM];
int c1[MAXM], c2[MAXM];
bool ins[MAXN];
vector<Edge> edges;
vector<int> G[MAXN];
int gcd(int a, int b)
{
	if (b==0) return a;
	return gcd(b, a%b);
}
void exgcd(int a, int b, int& x, int& y)
{
	if (b==0) x=1, y=0;
	else exgcd(b, a%b, y, x), y-=a/b*x;
}
int qpow(int a, int b)
{
	int r=1;
	while (b)
	{
		if (b&1) r=1ll*r*a%P;
		a=1ll*a*a%P; b>>=1;
	}
	return r;
}
int inv(int a)
{
	int x, y;
	exgcd(a, P, x, y);
	return (x%P+P)%P;
}
void init()
{
	memset(c, 0, sizeof c);
	c[0][0]=1;
	for (int i=1; i<=m+k; i++)
	{
		c[i][0]=1;
		for (int j=1; j<=i&&j<=m; j++)
			c[i][j]=(c[i-1][j-1]+c[i-1][j])%P;
	}
	memset(f, 0, sizeof f);
	for (int i=1; i<=m; i++)
	{
		for (int j=1; j<=i; j++)
			f[i]=(f[i]+qpow(k, gcd(i, j)))%P;
		f[i]=1ll*f[i]*inv(i)%P;
	}
	edges.clear();
	for (int i=1; i<=n; i++) G[i].clear();
	memset(dfn, 0, sizeof dfn);
	memset(ins, 0, sizeof ins);
	cnt=tot=t1=t2=0;
}
inline void addEdge(int u, int v)
{
	edges.push_back(Edge(u, v));
	edges.push_back(Edge(v, u));
	G[u].push_back(edges.size()-2);
	G[v].push_back(edges.size()-1);
}
void tarjan(int u, int f)
{
	low[u]=dfn[u]=++cnt; ins[u]=1;
	for (int i=0; i<G[u].size(); i++)
	{
		int v=edges[G[u][i]].to;
		if (!dfn[v]||v!=f&&ins[v])
		{
			s2[++t2]=G[u][i];
			if (!dfn[v])
			{
				s1[++t1]=v;
				tarjan(v, u);
				low[u]=min(low[u], low[v]);
				if (low[v]>=dfn[u])
				{
					c1[++tot]=1; c2[tot]=0;
					do c1[tot]++; while (s1[t1--]!=v);
					do c2[tot]++; while (s2[t2--]!=G[u][i]);
				}
			}
			else low[u]=min(low[u], dfn[v]);
		}
	}
	ins[u]=0;
}
int main()
{
//	freopen("B.in", "r", stdin);
//	freopen("B.out", "w", stdout);
	scanf("%d%d%d", &n, &m, &k);
	init();
	for (int i=1; i<=m; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		addEdge(u, v);
	}
	for (int i=1; i<=n; i++)
		if (!dfn[i]) tarjan(i, 0);
	int ans=1;
	for (int i=1; i<=tot; i++)
	{
		if (c1[i]==c2[i]) ans=1ll*ans*f[c2[i]]%P;
		else if (c1[i]<c2[i]) ans=1ll*ans*c[c2[i]+k-1][c2[i]]%P;
		else ans=1ll*ans*k%P;
	}
	printf("%d\n", ans);
	return 0;
}