// Ho-kago Tea Time

#include <bits/stdc++.h>

using namespace std;

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define fst first
#define snd second
#define SZ(u) ((int) (u).size())
#define ALL(u) (u).begin(), (u).end()

inline void proc_status()
{
	ifstream t("/proc/self/status");
	cerr << string(istreambuf_iterator<char>(t), istreambuf_iterator<char>()) << endl;
}

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<typename T> inline T read()
{
	register T sum(0), fg(1);
	register char ch(getchar());
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') fg = -1;
	for(;  isdigit(ch); ch = getchar()) sum = sum * 10 - '0' + ch;
	return sum * fg;
}

typedef long long LL;
typedef pair<int, int> pii;

const int MOD = (int) 1e9 + 7;

inline int fpm(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;
}

inline int inv(int x) { assert(x); return fpm(x, MOD - 2); }

const int MAXN = 50, MAXM = 100;

namespace MATH
{
	const int n = MAXM * 2;

	int fac[n + 5], ifac[n + 5];

	inline void init()
	{
		fac[0] = 1;
		for(int i = 1; i <= n; ++i) fac[i] = (LL) fac[i - 1] * i % MOD;
		ifac[n] = inv(fac[n]);
		for(int i = n - 1; i >= 0; --i) ifac[i] = (LL) ifac[i + 1] * (i + 1) % MOD;
	}

	inline int C(int N, int M) { return N < 0 || M < 0 || N < M ? 0 : (LL) fac[N] * ifac[N - M] % MOD * ifac[M] % MOD; }
	inline int div_into(int N, int M) { return C(N + M - 1, M - 1); }
}
using MATH::fac;
using MATH::ifac;
using MATH::C;
using MATH::div_into;

int n, m, k;

vector<int> adj[MAXN + 5];

inline void input()
{
	n = read<int>(), m = read<int>(), k = read<int>();
	for(int i = 1; i <= m; ++i)
	{
		int u = read<int>(), v = read<int>();
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
}

struct edge
{
	int u, v;

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

int dfn[MAXN + 5], low[MAXN + 5], dfn_cur = 0;
vector<edge> stk;

int size[MAXN + 5], cnt = 0;
vector<edge> E[MAXN + 5];

inline void extract_BCC(int u, int v)
{
	static int vis[MAXN + 5];

	size[++cnt] = 0;
	while(!stk.empty())
	{
		int p = stk.back().u, q = stk.back().v;
		stk.pop_back();

		size[cnt] += chkmax(vis[p], cnt);
		size[cnt] += chkmax(vis[q], cnt);
		E[cnt].emplace_back(p, q);
		if(p == u && q == v) break;
	}
}

inline void dfs_BCC(int u, int fa)
{
	low[u] = dfn[u] = ++dfn_cur;

	for(auto v : adj[u]) if(v != fa)
	{
		if(!dfn[v])
		{
			stk.emplace_back(u, v);
			dfs_BCC(v, u);
			chkmin(low[u], low[v]);

			if(low[v] >= dfn[u]) extract_BCC(u, v);
		}
		else if(dfn[v] < dfn[u]) stk.emplace_back(v, u), chkmin(low[u], dfn[v]);
	}
}

inline void solve()
{
	for(int i = 1; i <= n; ++i) if(!dfn[i])
	{
		dfs_BCC(i, 0);
		if(!stk.empty()) extract_BCC(0, 0);
	}

	int ans = 1;
	for(int i = 1; i <= cnt; ++i)
		if(SZ(E[i]) == 1) ans = (LL) ans * k % MOD;
		else if(SZ(E[i]) == size[i])
		{
			int res = 0;
			for(int j = 1; j <= size[i]; ++j) (res += fpm(k, __gcd(j, size[i]))) %= MOD;
			res = (LL) res * inv(size[i]) % MOD;
			ans = (LL) ans * res % MOD;
		}
		else ans = (LL) ans * div_into(SZ(E[i]), k) % MOD;

	printf("%d\n", (ans + MOD) % MOD);
}

int main()
{
#ifdef K_ON // K-ON!
	freopen("F.in", "r", stdin);
	freopen("F.out", "w", stdout);
#endif

	MATH::init();
	input();
	solve();

	return 0;
}



Measured memory_bytes: 256