#include <bits/stdc++.h>

typedef long long ll;
const int N = 54, M = 216, mod = 1000000007;
const int phi[N] = {0, 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12, 18, 12, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18, 24, 16, 40, 12, 42, 20, 24, 22, 46, 16, 42, 20, 32, 24, 52};

struct edge {
	int u, v;
	edge (int u0 = 0, int v0 = 0) : u(u0), v(v0) {}
} e[M];

int V, E, C, Es = 0, Br;
int first[N], next[M];
int cnt = 0, id[N], low[N];
int top = 0, stack[N], size[N];
int bcc_cnt = 0, p[M], vi[M], ei[M];
int fact[M], finv[M], polya[M];

inline void down(int &x, const int y) {x > y ? x = y : 0;}
ll PowerMod(ll a, int n, ll c = 1) {for (; n; n >>= 1, a = a * a % mod) if (n & 1) c = c * a % mod; return c;}

void init(int m) {
	int i, j, ij, mm = m;
	for (*fact = i = 1; i < M; ++i) fact[i] = (ll)fact[i - 1] * i % mod;
	--i, finv[i] = PowerMod(fact[i], mod - 2);
	for (; i; --i) finv[i - 1] = (ll)finv[i] * i % mod;
	for (i = 1; i < N; ++i, mm = (ll)mm * m % mod)
		for (j = 1, ij = i; ij < N; ++j, ij += i)
			polya[ij] = (polya[ij] + (ll)mm * phi[j]) % mod;
	for (i = 1; i < N; ++i) polya[i] = (ll)fact[i - 1] * finv[i] % mod * polya[i] % mod;
}

inline ll binom(int n, int r) {return (ll)fact[n] * finv[r] % mod * finv[n - r] % mod;}

inline void addedge(int u, int v) {
	e[++Es] = edge(u, v), next[Es] = first[u], first[u] = Es;
	e[++Es] = edge(v, u), next[Es] = first[v], first[v] = Es;
}

void dfs(int x, int px = 0) {
	int i, y, z;
	id[x] = low[x] = ++cnt, stack[top++] = x;
	for (i = first[x]; i; i = next[i])
		if (!id[y = e[i].v]) {
			dfs(y, i), down(low[x], low[y]);
			if (id[x] == low[y])
				for (p[++bcc_cnt + V] = x, vi[bcc_cnt] = 1, z = 0; z != y; )
					p[z = stack[--top]] = bcc_cnt + V, ++vi[bcc_cnt];
			else if (id[x] < low[y]) ++Br, --top;
		} else if (px - 1 ^ i - 1 ^ 1)
			down(low[x], id[y]);
}

int main() {
	int i, u, v, b, ans = 1;
	scanf("%d%d%d", &V, &E, &C), init(C);
	for (i = 0; i < E; ++i) scanf("%d%d", &u, &v), addedge(u, v);
	for (i = 1; i <= V; ++i) if (!id[i]) dfs(i);
	for (i = 1; i <= Es; i += 2) {
		u = e[i].u, v = e[i].v;
		if ((p[u] && p[u] == p[v]) || p[p[u]] == v || p[p[v]] == u)
			b = p[p[p[v]] == u ? v : u] - V, ++ei[b];
	}
	for (i = 1; i <= bcc_cnt; ++i)
		if (vi[i] < ei[i]) ans = ans * binom(ei[i] + C - 1, ei[i]) % mod;
		else assert(vi[i] == ei[i]), ans = (ll)ans * polya[ei[i]] % mod;
	printf("%d\n", (int)PowerMod(C, Br, ans));
	return 0;
}