/********************************************************************************
	
	Code by a weak man who named CYJian, and he hopes the code can get more points.

	Algorithm: 

 ********************************************************************************/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

//{{{ FAST IO AND SOME FUNCTIONS
const int __SIZE = 1 << 18;
char ibuf[__SIZE], *iS, *iT;

#define ge (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++)
#define ri read_int()
#define rl read_ll()
#define ra read_alpha()
#define FILE(s) freopen(s"in", "r", stdin), freopen(s"out", "w", stdout)

template<typename T>
inline void read(T &x) {
	char ch, t = 0; x = 0;
	while(!isdigit(ch = ge)) t |= ch == '-';
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = ge;
	x = t ? -x : x;
}
inline char read_alpha() { char c = ge; while(!isalpha(c) && c != EOF) c = ge; return c; }
inline int read_int() { int x; return read(x), x; }
inline ll read_ll() { ll x; return read(x), x; }

template<typename T> inline void chkmin(T&a, T b) { a = a < b ? a : b; }
template<typename T> inline void chkmax(T&a, T b) { a = a > b ? a : b; }
//}}}

const int MAXN = 210;
const int mod = 1e9 + 7;

int cnt;
int pw[MAXN];
int inv[MAXN];
int fac[MAXN];
int pri[MAXN];
int chk[MAXN];
int phi[MAXN];
int ans[MAXN];
int ifac[MAXN];

inline int Binom(int n, int m) { return 1LL * fac[n] * ifac[m] % mod * ifac[n - m] % mod; }

inline void init(int k) {
	int n = 200; pw[1] = k;
	pw[0] = ifac[0] = fac[0] = 1;
	inv[1] = ifac[1] = fac[1] = 1;
	for(int i = 2; i <= n; i++) {
		pw[i] = 1LL * pw[i - 1] * k % mod;
		fac[i] = 1LL * fac[i - 1] * i % mod;
		inv[i] = 1LL * (mod - mod / i) * inv[mod % i] % mod;
		ifac[i] = 1LL * ifac[i - 1] * inv[i] % mod;
	} phi[1] = 1;
	for(int i = 2; i <= n; i++) {
		if(!chk[i]) pri[++cnt] = i, phi[i] = i - 1;
		for(int j = 1; j <= cnt; j++) {
			if(i * pri[j] > n) break;
			chk[i * pri[j]] = 1;
			if(i % pri[j] == 0) {
				phi[i * pri[j]] = phi[i] * pri[j];
				break;
			} phi[i * pri[j]] = phi[i] * (pri[j] - 1);
		}
	}
	for(int i = 1; i <= n; i++)
		for(int j = i, k = 1; j <= n; j += i, ++k)
			ans[j] = (ans[j] + 1LL * phi[i] * pw[k]) % mod;
	for(int i = 1; i <= n; i++) ans[i] = 1LL * ans[i] * inv[i] % mod;
}

struct Edge {
	int u, v;

	Edge() {}
	Edge(int u, int v):u(u), v(v) {}
}E[MAXN];

int tot;
int fi[MAXN];
int ne[MAXN];
int to[MAXN];

inline void Link(int u, int v) {
	tot++;
	to[tot] = v;
	ne[tot] = fi[u];
	fi[u] = tot;
}

int tim;
int dfn[MAXN];
int low[MAXN];

int top;
Edge sta[MAXN];

int C;
int col[MAXN];
int szn[MAXN];
int sze[MAXN];

inline void Tarjan(int x, int la = 0) {
	dfn[x] = low[x] = ++tim;
	for(int i = fi[x]; i; i = ne[i]) {
		int u = to[i];
		if(u == la) continue;
		if(!dfn[u]) {
			sta[++top] = Edge(x, u);
			Tarjan(u, x);
			chkmin(low[x], low[u]);
			if(low[u] >= dfn[x]) {
				++C;
				while(1919810) {
					int a = sta[top].u;
					int b = sta[top].v;
					++sze[C], --top;
					if(col[a] != C) col[a] = C, ++szn[C];
					if(col[b] != C) col[b] = C, ++szn[C];
					if(x == a && u == b) break;
				}
			}
		} else if(dfn[u] < dfn[x]) {
			sta[++top] = Edge(x, u);
			chkmin(low[x], dfn[u]);
		}
	}
}

int main() {
#ifdef LOCAL
	FILE("");
#endif
	int n = ri, m = ri, k = ri;
	init(k);
	for(int i = 1; i <= m; i++) {
		E[i].u = ri, E[i].v = ri;
		Link(E[i].u, E[i].v);
		Link(E[i].v, E[i].u);
	}
	for(int i = 1; i <= n; i++) if(!dfn[i]) Tarjan(i);
	int res = 1;
	for(int i = 1; i <= C; i++)
		if(szn[i] < sze[i]) res = 1LL * res * Binom(sze[i] + k - 1, k - 1) % mod;
		else res = 1LL * res * ans[sze[i]] % mod;
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 256