#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 55, M = 288, Mod = 1e9 + 7;

inline int Pow(int x, int y, int res = 1) {
	for (; y; y >>= 1, x = (LL)x * x % Mod)
		if (y & 1) res = (LL)res * x % Mod;
	return res % Mod;
}
inline int Inv(int x) { return Pow(x, Mod - 2); }

int gcd(int x, int y) {
	if (!y) return x;
	return gcd(y, x % y);
}

int dex, Top, cnt, dfn[N], low[N], cntv[N], cnte[N];
int n, m, K, tot, pw[N], bel[N], Head[N], Next[M], Adj[M], f[M][M];
pair<int, int> S[M + 1 /* not N!!! */];

vector<int> vt[N];

void Tarjan(int x, int fat) {
	dfn[x] = low[x] = ++dex;
	for (int e = Head[x]; e; e = Next[e])
		if (Adj[e] != fat) {
			if (dfn[Adj[e]] == -1) {
				S[++Top] = make_pair(x, Adj[e]);
				Tarjan(Adj[e], x);
				low[x] = min(low[x], low[Adj[e]]); /* ! */
				if (low[Adj[e]] >= dfn[x]) {
					++cnt;
					while (1) {
						int nx = S[Top].first, ny = S[Top].second;
						--Top, ++cnte[cnt];
						if (bel[nx] != cnt) bel[nx] = cnt, ++cntv[cnt];
						if (bel[ny] != cnt) bel[ny] = cnt, ++cntv[cnt];
						if (nx == x && ny == Adj[e]) break;
					}
				}
			} else if (dfn[x] > dfn[Adj[e]])
				S[++Top] = make_pair(x, Adj[e]), low[x] = min(low[x], dfn[Adj[e]]);
		}
}

int main()
{
	scanf("%d%d%d", &n, &m, &K), pw[0] = 1;
	for (int i = 1; i <= n; ++i) pw[i] = (LL)pw[i - 1] * K % Mod;
	for (int i = 1, x, y; i <= m; ++i) {
		scanf("%d%d", &x, &y);
		Next[++tot] = Head[x]; Head[x] = tot; Adj[tot] = y;
		Next[++tot] = Head[y]; Head[y] = tot; Adj[tot] = x;
	}
	memset(dfn, -1, sizeof(dfn)), memset(low, -1, sizeof(low));
	for (int i = 1; i <= n; ++i)
		if (dfn[i] == -1) {
			dex = 0;
			Tarjan(i, 0);
		}
	f[0][0] = 1;
	for (int i = 1; i <= K; ++i) {
		int sum = 0;
		for (int j = 0; j <= m; ++j)
			sum = (sum + (LL)f[i - 1][j]) % Mod;
		for (int j = m; j >= 0; --j) {
			f[i][j] = (sum % Mod + Mod) % Mod;
			sum = (sum - f[i - 1][j] + Mod) % Mod;
		}
	} /* (1 / (1 - x)) ^ K */
	int fans = 1;
	for (int i = 1; i <= cnt; ++i) {
		if (cnte[i] == 1) fans = (LL)fans * K % Mod;
		else if (cntv[i] == cnte[i]) {
			int sum = pw[cnte[i]];
			for (int j = 1; j < cnte[i]; ++j)
				sum = (sum + (LL)pw[gcd(cnte[i], j)]) % Mod;
			sum = (LL)sum * Inv(cnte[i] /* n */) % Mod;
			fans = (LL)fans * sum % Mod;
		} else {
			fans = (LL)fans * f[K][cnte[i]] % Mod;
		//	printf("%d %d %d\n", cnte[i], K, f[K][cnte[i]]);
		}
	}
	printf("%d\n", (fans % Mod + Mod) % Mod);
	
	return 0;
}
