#include <bits/stdc++.h>
using namespace std;

template<int MOD>
struct mod_int {
	static const int mod = MOD;
	unsigned x;
	mod_int() : x(0) { }
	mod_int(int sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }
	mod_int(long long sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }
	int get() const { return (int)x; }

	mod_int &operator+=(mod_int that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
	mod_int &operator-=(mod_int that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
	mod_int &operator*=(mod_int that) { x = (unsigned long long)x * that.x % MOD; return *this; }
	mod_int &operator/=(mod_int that) { return *this *= that.inverse(); }

	mod_int operator+(mod_int that) const { return mod_int(*this) += that; }
	mod_int operator-(mod_int that) const { return mod_int(*this) -= that; }
	mod_int operator*(mod_int that) const { return mod_int(*this) *= that; }
	mod_int operator/(mod_int that) const { return mod_int(*this) /= that; }

	mod_int inverse() const {
		long long a = x, b = MOD, u = 1, v = 0;
		while (b) {
			long long t = a / b;
			a -= t * b; swap(a, b);
			u -= t * v; swap(u, v);
		}
		return mod_int(u);
	}
};

template<int MOD>
istream& operator >> (istream& is, mod_int<MOD>& val) {
	long long x;
	is >> x; val = x;
	return is;
}

template<int MOD>
ostream& operator << (ostream& os, const mod_int<MOD>& val) {
	os << val.get();
	return os;
}

using mint = mod_int<1000000007>;

const int MAX = 2e6;

bool inited = false;
mint fac[MAX + 1];
mint rfac[MAX + 1];

void init() {
	inited = true;
	fac[0] = 1;
	for (int i = 1; i <= MAX; i++) {
		fac[i] = fac[i - 1] * i;
	}
	rfac[MAX] = fac[MAX].inverse();
	for (int i = MAX; i >= 1; i--) {
		rfac[i - 1] = rfac[i] * i;
	}
}

mint nPr(int n, int r) {
	if (!inited) init();
	return r < 0 || n < r ? 0 : fac[n] * rfac[n - r];
}

mint nCr(int n, int r) {
	if (!inited) init();
	return r < 0 || n < r ? 0 : fac[n] * rfac[n - r] * rfac[r];
}

mint nHr(int n, int r) {
	if (!inited) init();
	return r == 0 ? 1 : nCr(n + r - 1, r);
}

using graph = vector<vector<int>>;

struct edge {
	int from, to;
	edge(int a, int b) : from(a), to(b) {}
};

bool operator < (const edge& l, const edge& r) {
	if (min(l.from, l.to) != min(r.from, r.to))
		return min(l.from, l.to) < min(r.from, r.to);
	return max(l.from, l.to) < max(r.from, r.to);
}

void visit(const graph &g, int v,
	vector<int>& art, vector<set<edge>>& bcomp,
	stack<edge>& S, vector<int>& num, vector<int>& low, int& time) {
	low[v] = num[v] = ++time;
	for (int w : g[v]) {
		if (num[w] < num[v]) S.emplace(v, w);
		if (num[w] == 0) {
			visit(g, w, art, bcomp, S, num, low, time);
			low[v] = min(low[v], low[w]);
			if ((num[v] == 1 && num[w] != 2) ||
				(num[v] != 1 && low[w] >= num[v])) art.push_back(v);
			if (low[w] >= num[v]) {
				bcomp.push_back(set<edge>());
				while (1) {
					edge f = S.top(); S.pop();
					bcomp.back().insert(f);
					if (f.from == v && f.to == w) break;
				}
			}
		}
		else low[v] = min(low[v], num[w]);
	}
}

pair<vector<int>, vector<set<edge>>> biconnected_component(const graph& g) {
	const int n = g.size();
	vector<int> art;
	vector<set<edge>> bcomp;
	vector<int> low(n), num(n);
	stack<edge> S;
	for (int u = 0; u < n; u++) if (num[u] == 0) {
		int time = 0;
		visit(g, u, art, bcomp, S, num, low, time);
	}
	sort(art.begin(), art.end());
	art.erase(unique(art.begin(), art.end()), art.end());
	return make_pair(art, bcomp);
}

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int N, M, K;
	cin >> N >> M >> K;
	graph G(N);
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b; --a, --b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	vector<int> art;
	vector<set<edge>> bcc;
	tie(art, bcc) = biconnected_component(G);
	vector<bool> is_art(N);
	for (auto v : art) is_art[v] = true;
	mint res = 1;
	for (int i = 0; i < (int)bcc.size(); i++) {
		int m = bcc[i].size();
		if (m == 1) {
			res *= K;
			continue;
		}
		vector<int> vs;
		for (const auto& e : bcc[i]) {
			vs.push_back(e.from);
			vs.push_back(e.to);
		}
		sort(vs.begin(), vs.end());
		vs.erase(unique(vs.begin(), vs.end()), vs.end());
		if ((int)vs.size() == m) {
			mint sum = 0;
			for (int j = 0; j < m; j++) {
				int g = __gcd(j, m);
				mint val = 1;
				for (int k = 0; k < g; k++) {
					val *= K;
				}
				sum += val;
			}
			res *= sum / m;
			continue;
		}
		res *= nCr(m + K - 1, K - 1);
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 15872