#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#define llint long long
#define mod 1000000007

using namespace std;

typedef pair<int, int> P;

int n, m, k;
vector<int> G[100005];

int V;
int pre[100005], low[100005];
vector<int> artvec;
vector<vector<P> > compvec;

int vid;
int lowlink_dfs(int v, int p)
{
	pre[v] = vid++;
	int ret = pre[v];
	for(int i = 0; i < G[v].size(); i++){
		if(G[v][i] == p) continue;
		if(pre[G[v][i]]) ret = min(ret, pre[G[v][i]]);
		else ret = min(ret, lowlink_dfs(G[v][i], v));
	}
	return low[v] = ret;
}

bool art_used[100005];
void art_dfs(int v, int p, int c)
{
	art_used[v] = true;
	bool flag = false;
	
	if(p == -1){
		bool first = true;
		for(int i = 0; i < G[v].size(); i++){
			if(G[v][i] == p) continue;
			if(art_used[G[v][i]] && pre[v] < pre[G[v][i]]) continue;
			if(!first) flag = true;
			compvec.push_back(vector<P>());
			compvec.back().push_back(P(v, G[v][i]));
			if(!art_used[G[v][i]]) art_dfs(G[v][i], v, (int)compvec.size()-1);
			first = false;
		}
	}
	else{
		for(int i = 0; i < G[v].size(); i++){
			if(G[v][i] == p) continue;
			if(art_used[G[v][i]] && pre[v] < pre[G[v][i]]) continue;
			if(low[G[v][i]] < pre[v]){
				compvec[c].push_back(P(v, G[v][i]));
				if(!art_used[G[v][i]]) art_dfs(G[v][i], v, c);
			}
			else{
				flag = true;
				compvec.push_back(vector<P>());
				compvec.back().push_back(P(v, G[v][i]));
				if(!art_used[G[v][i]]) art_dfs(G[v][i], v, (int)compvec.size()-1);
			}
		}
	}
	if(flag) artvec.push_back(v);
}

//すべて関節点をartvecに格納する。compvec[i]にi番目の二重頂点連結成分の辺をすべて格納する。
void findArticulationPoints()
{
	vid = 1;
	for(int i = 1; i <= V; i++){
		if(!pre[i]) lowlink_dfs(i, -1);
	}
	
	artvec.clear(), compvec.clear();
	for(int i = 1; i <= V; i++) art_used[i] = false;
	for(int i = 1; i <= V; i++){
		if(!art_used[i]) art_dfs(i, -1, 0);
	}
}

const int FACT_MAX = 200005;
llint fact[FACT_MAX], fact_inv[FACT_MAX];

llint modpow(llint a, llint n)
{
	if(n == 0) return 1;
	if(n % 2){
		return ((a%mod) * (modpow(a, n-1)%mod)) % mod;
	}
	else{
		return modpow((a*a)%mod, n/2) % mod;
	}
}

void make_fact()
{
	llint val = 1;
	fact[0] = 1;
	for(int i = 1; i < FACT_MAX; i++){
		val *= i;
		val %= mod;
		fact[i] = val;
	}
	fact_inv[FACT_MAX-1] = modpow(fact[FACT_MAX-1], mod-2);
	for(int i = FACT_MAX-2; i >= 0; i--){
		fact_inv[i] = fact_inv[i+1] * (i+1) % mod;
	}
}

llint comb(llint n, llint k)
{
	llint ret = 1;
	ret *= fact[n];
	ret *= fact_inv[k], ret %= mod;
	ret *= fact_inv[n-k], ret %= mod;
	return ret;
}

llint gcd(llint a, llint b)
{
	if(b == 0) return a;
	return gcd(b, a%b);
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m >> k;
	make_fact();
	
	int u, v;
	for(int i = 1; i <= m; i++){
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	
	V = n;
	findArticulationPoints();
	
	/*for(int i = 0; i < artvec.size(); i++) cout << artvec[i] << " "; cout << endl;
	for(int i = 0; i < compvec.size(); i++){
		cout << i << " : ";
		for(int j = 0; j < compvec[i].size(); j++){
			cout << "(" << compvec[i][j].first << ", " << compvec[i][j].second << ") ";
		}
		cout << endl;
	}*/
	
	llint ans = 1;
	for(int i = 0; i < compvec.size(); i++){
		if(compvec[i].size() == 1){
			ans *= k, ans %= mod;
			continue;
		}
		map<int, int> mp;
		for(int j = 0; j < compvec[i].size(); j++){
			mp[compvec[i][j].first]++;
			mp[compvec[i][j].second]++;
		}
		bool flag = true;
		for(auto it = mp.begin(); it != mp.end(); it++){
			if(it->second != 2) flag = false;
		}
		int s = compvec[i].size();
		if(!flag){
			ans *= comb(s+k-1, s), ans %= mod;
			continue;
		}
		llint sum = 0;
		for(int i = 0; i < s; i++){
			sum += modpow(k, gcd(s, i)), sum %= mod;
		}
		sum *= modpow(s, mod-2), sum %= mod;
		ans *= sum, ans %= mod;
	}
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 6656