
#include <set>
#include <stack>
#include <cstdio>

using namespace std;
const int MOD(1000000000 + 7);
typedef long long int LL;

constexpr int Mult(int a, int b)
{
	return (a * 1LL) * b % MOD;
}

constexpr int Add(int a, int b)
{
	return a + b >= MOD ? a + b - MOD : a + b;
}

constexpr int Sub(int a, int b)
{
	return a - b < 0 ? a - b + MOD : 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 -= x * (a / b);
}

inline int inverse(int a)
{
	int invx, invy;
	exgcd(a, MOD, invx, invy);
	return (invx % MOD + MOD) % MOD;
}

int power(int a, int n)
{
	int Ret(1);
	while (n)
	{
		if (n & 1)
			Ret = Mult(Ret, a);
		a = Mult(a, a), n >>= 1;
	}
	return Ret;
}

int gcd(int a, int b)
{
	return b == 0 ? a : gcd(b, a % b);
}

/*
每个点双的情况是独立的，对每个点双分别计数乘起来就是答案。对于一个点双的答案，分情况讨论：
(1)这个点双是一条边。那么方案数 = K
(2)这个点双是一个环，根据polya定理，设点数是n，方案数 = Sum{K^gcd(n, i)   |   0 <= i <= n - 1} / n
(3)这个点双有多个环。可以对于两个相交的环进行操作，交换任意两条相邻的边，同时不改变其它边的颜色。那么方案是什么只和每种颜色的数量有关，方案数是一个不定方程的解数 
*/

const int Max_N(55);
const int Max_M(105);
const int Max_K(105);

int N, M, K, Head[Max_N], Total, To[Max_M << 1], Next[Max_M << 1], Ans = 1, C[Max_M + Max_K][Max_M + Max_K];

struct edge
{
	edge(const int &_u, const int &_v) : u(_u), v(_v) {}
	int u, v;
};

inline void Add_Edge(int s, int t)
{
	++Total, To[Total] = t, Next[Total] = Head[s], Head[s] = Total;
}

stack<edge> S;
int dfsclock, Pre[Max_N], bcctot, bccno[Max_N], V[Max_N + Max_M], E[Max_N + Max_M];
int Tarjan(int u, int fa)
{
	int lowu(Pre[u] = ++dfsclock), lowv;
	for (int i = Head[u], v;i;i = Next[i])
	{
		edge e(u, v = To[i]);
		if (!Pre[v])
		{
			S.push(e), lowu = min(lowu, lowv = Tarjan(v, u));
			if (lowv >= Pre[u])
			{
				++bcctot;
				while (true)
				{
					e = S.top(), S.pop();
					if (bccno[e.u] != bcctot)
						++V[bccno[e.u] = bcctot];
					if (bccno[e.v] != bcctot)
						++V[bccno[e.v] = bcctot];
					++E[bcctot];
					if (u == e.u && v == e.v)
						break;
				}
			}
		}
		else
			if (Pre[v] < Pre[u] && v != fa)
				S.push(e), lowu = min(lowu, Pre[v]);
	}
	return lowu;
}

int main()
{
	scanf("%d%d%d", &N, &M, &K);
	C[0][0] = 1;
	for (int i = 1;i <= M + K;++i)
	{
		C[i][0] = C[i][i] = 1;
		for (int j = 1;j < i;++j)
			C[i][j] = Add(C[i - 1][j - 1], C[i - 1][j]);
	}
	for (int u, v;M--;)
		scanf("%d%d", &u, &v), Add_Edge(u, v), Add_Edge(v, u);
	for (int i = 1;i <= N;++i)
		if (!Pre[i])
			Tarjan(i, -1);
	for (int i = 1, Ret;i <= bcctot;++i)
	{
		if (E[i] == 1)
		{
			Ans = Mult(Ans, K);
			continue;
		}
		if (V[i] == E[i])
		{
			Ret = 0;
			for (int j = 0;j <= V[i] - 1;++j)
				Ret = Add(Ret, power(K, gcd(V[i], j)));
			Ans = Mult(Ans, Ret = Mult(Ret, inverse(V[i])));
			continue;
		}
		Ans = Mult(Ans, C[E[i] + K - 1][K - 1]);
	}
	printf("%d", Ans);
	return 0;
}