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

typedef pair<int, int> pii;
typedef long long ll;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()
#define dump(x) cout << #x << " = " << (x) << endl
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

template<class T, class U> void chmin(T& t, const U& u) { if (t > u) t = u; }
template<class T, class U> void chmax(T& t, const U& u) { if (t < u) t = u; }

template<class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	os<<"{";
	rep(i, v.size()) {
		if (i) os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

const ll MOD = TEN(9) + 7;
const int maxn = 100010;

int N, M, K;
V<int> g[maxn];

int col[maxn];
ll dp[maxn][3]; //diff
ll dpc[maxn][2]; //same
ll ans;

void add(int num, const V<pair<pii,int>>& es) {
	ll u = 1;

	for (auto e : es) {
		int a = e.fi.fi, b = e.fi.se, len = e.se;
		if (len == 0) {
			if (col[a] == col[b]) {
				return ;
			}
		} else {
			if (col[a] == col[b]) {
				u = u * dpc[len][0] % MOD;
			} else {
				if (len >= 2) {
					u = u * (dp[len][0] + dp[len][1]) % MOD;
				} else {
					u = u * dp[len][0] % MOD;
				}
			}
		}
	}
	int now = *max_element(col, col + N);
	if (now >= K) return ;
	for (int i = 0; i <= now; ++i) {
		u = u * (K - i) % MOD;
	}
	ans = (ans + u) % MOD;
}

void dfs(int p, int num, const V<pair<pii,int>>& es) {
	if (p == num) {
		add(num, es);
		return ;
	}
	set<int> st;
	rep(i, p) {
		if (!st.count(col[i])) {
			col[p] = col[i];
			dfs(p + 1, num, es);
			st.insert(col[i]);
		}
	}
	int now = 0;
	while (st.count(now)) {
		now++;
	}
	col[p] = now;
	dfs(p + 1, num, es);
}

set<int> st[maxn];

void solve() {
	dp[1][2] = 1;
	dp[1][0] = K - 2;
	for (int i = 1; i < maxn - 1; ++i) {
		if (K >= 3) {
			(dp[i+1][0] += dp[i][0] * (K-3)) %= MOD;
		}
		(dp[i+1][1] += dp[i][0]) %= MOD;
		(dp[i+1][2] += dp[i][0]) %= MOD;
		(dp[i+1][0] += dp[i][1] * (K-2)) %= MOD;
		(dp[i+1][2] += dp[i][1]) %= MOD;
		(dp[i+1][0] += dp[i][2] * (K-2)) %= MOD;
		(dp[i+1][1] += dp[i][2]) %= MOD;		
	}

	dpc[1][0] = K - 1;

	for (int i = 1; i < maxn - 1; ++i) {
		(dpc[i+1][0] += dpc[i][0] * (K - 2)) %= MOD;
		(dpc[i+1][1] += dpc[i][0]) %= MOD;
		(dpc[i+1][0] += dpc[i][1] * (K - 1)) %= MOD;
	}

	rep(i, N) {
		for (int to : g[i]) {
			st[i].insert(to);
		}
	}
	queue<int> que;
	int leaf = 0;
	rep(i, N) if (st[i].size() == 1) {
		que.push(i);
	}
	while (!que.empty()) {
		int v = que.front(); que.pop();
		for (auto to : st[v]) {
			st[to].erase(v);
			if (st[to].size() == 1) {
				que.push(to);
			}
		}
		st[v].clear();
		++leaf;
	}

	V<int> special;
	V<int> rid(N, -1);
	int now = 0;
	rep(i, N) {
		if (st[i].size() >= 3) {
			rid[i] = now++;
			special.pb(i);
		}
	}
	if (special.size() == 0) {
		rep(i, N) {
			if (st[i].size() == 2) {
				rid[i] = now++;
				special.pb(i);
				break;
			}
		}
	}
	//dump(special);

	V<pair<pii, int>> es;

	V<int> vis(N);
	for (int v : special) {
		for (auto to : st[v]) {
			if (vis[to]) continue;
			int cur = to;
			int num = 0;
			int pr = v;
			while (rid[cur] == -1) {
				vis[cur] = 1;
				for (auto t : st[cur]) {
					if (t != pr) {
						pr = cur;
						cur = t;
						break;
					}
				}
				++num;
			}
			es.eb(mp(rid[v], rid[cur]), num);
			//printf("%d---%d, len=%d\n", rid[v], rid[cur], num);
		}
	}

	ans = 0;
	dfs(0, special.size(), es);
	//dump(leaf);

	rep(i, leaf) ans = ans * (K - 1) % MOD;
	cout << ans << endl;	
}

int main() {
	cin >> N >> M >> K;
	rep(i, M) {
		int a, b;
		cin >> a >> b;
		--a; --b;
		g[a].pb(b);
		g[b].pb(a);
	}

	if (K == 1 && N >= 2) {
		puts("0");
		return 0;
	}

	if (M == N-1) {
		ll ans = K;
		rep(i, N-1) {
			ans = ans * (K - 1) % MOD;
		}
		cout << ans << endl;
		return 0;
	}

	solve();

	return 0;
}