#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 全体
int N, M, K;
int A[1 << 18], B[1 << 18]; bool bridge[1 << 18];
vector<pair<int, int>> X[1 << 17];
vector<int> Y[1 << 17];
int val[109][109];
int col[109], cntv;

// nCr を求める
long long nr[1009][1009];
long long mod = 1000000007;

// 最短距離の計算
int dst[109][109], prevx[109][109];

// 数学的計算
void init() {
	for (int i = 0; i <= 1000; i++) {
		for (int j = 0; j <= 1000; j++) {
			if (i == 0 || j == 0) nr[i][j] = 1;
			else nr[i][j] = (nr[i - 1][j] + nr[i][j - 1]) % mod;
		}
	}
}

long long modpow(long long a, long long b, long long m) {
	long long p = 1, q = a;
	for (int i = 0; i < 33; i++) {
		if ((b / (1LL << i)) % 2 == 1) { p *= q; p %= m; }
		q *= q; q %= m;
	}
	return p;
}

long long Div(long long a, long long b, long long m) {
	return (a * modpow(b, m - 2, m)) % m;
}

long long counts(int pos) {
	long long dp[109];
	for (int i = 0; i <= 100; i++) dp[i] = 0;

	long long r = 1;
	for (int i = 1; i <= pos; i++) {
		r *= (1LL * K); r %= mod;
		if (pos % i != 0) continue;

		dp[i] = r;
		for (int j = 1; j <= i - 1; j++) {
			if (i % j == 0) dp[i] -= dp[j];
		}
		dp[i] = (dp[i] + mod * mod) % mod;
	}

	long long cnt = 0;
	for (int i = 1; i <= pos; i++) cnt += Div(dp[i], i, mod);
	return cnt % mod;
}

void shortests() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) { dst[i][j] = (1 << 30); prevx[i][j] = -1; }
		dst[i][i] = 0;
		for (int t = 1; t <= N; t++) {
			for (int j = 1; j <= N; j++) {
				for (int k : Y[j]) {
					if (dst[i][k] <= dst[i][j] + 1) continue;
					dst[i][k] = dst[i][j] + 1;
					prevx[i][k] = j;
				}
			}
		}
	}
}

vector<int> shortest_path(int u, int v) {
	int cx = v; vector<int> E;
	while (cx != u) {
		int f = prevx[u][cx];
		E.push_back(val[f][cx]);
		cx = f;
	}
	return E;
}

class UnionFind {
public:
	vector<int> par;
	
	void init(int sz) {
		par.resize(sz, -1);
	}
	int root(int pos) {
		if (par[pos] == -1) return pos;
		par[pos] = root(par[pos]);
		return par[pos];
	}
	void unite(int u, int v) {
		u = root(u); v = root(v);
		if (u == v) return;
		par[u] = v;
	}
	bool same(int u, int v) {
		if (root(u) == root(v)) return true;
		return false;
	}
};

int main() {
	cin >> N >> M >> K;
	for (int i = 1; i <= M; i++) {
		cin >> A[i] >> B[i];
		X[A[i]].push_back(make_pair(B[i], i));
		X[B[i]].push_back(make_pair(A[i], i));
		val[A[i]][B[i]] = i;
		val[B[i]][A[i]] = i;
	}
	init();

	UnionFind UF0; UF0.init(N + 2);
	for (int i = 1; i <= M; i++) {
		if (UF0.same(A[i], B[i]) == true) continue;
		Y[A[i]].push_back(B[i]);
		Y[B[i]].push_back(A[i]);
		UF0.unite(A[i], B[i]);
	}
	shortests();

	UnionFind UF1; UF1.init(N + 2);
	UnionFind UF2; UF2.init(M + 2);
	for (int i = 1; i <= M; i++) {
		if (UF1.same(A[i], B[i]) == false) {
			UF1.unite(A[i], B[i]);
		}
		else {
			vector<int> R = shortest_path(A[i], B[i]);
			for (int j : R) UF2.unite(i, j);
		}
	}

	// 最後
	for (int i = 1; i <= M; i++) {
		if (col[i] >= 1) continue;
		cntv++;
		for (int j = 1; j <= M; j++) {
			if (col[j] >= 1) continue;
			if (UF2.same(i, j) == true) col[j] = cntv;
		}
	}

	long long ans = 1;
	for (int i = 1; i <= cntv; i++) {
		vector<int> E2, E1;
		for (int j = 1; j <= M; j++) { if (col[j] == i) { E2.push_back(j); E1.push_back(A[j]); E1.push_back(B[j]); } }
		sort(E1.begin(), E1.end());
		E1.erase(unique(E1.begin(), E1.end()), E1.end());
		int cnt1 = E1.size();
		int cnt2 = E2.size();
		
		if (cnt1 > cnt2) {
			ans *= (1LL * K);
			ans %= mod;
		}
		else if (cnt1 == cnt2) {
			ans *= counts(cnt1);
			ans %= mod;
		}
		else {
			ans *= nr[K - 1][cnt2];
			ans %= mod;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 16640