#include <bits/stdc++.h>
#define endl '\n'

//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")

using namespace std;
template<class T, class T2> inline void chkmax(T &x, const T2 &y) { if(x < y) x = y; }
template<class T, class T2> inline void chkmin(T &x, const T2 &y) { if(x > y) x = y; }
const int MAXN = (1 << 20);
const int mod = (int)1e9 + 7;

int n, m, k;
vector<int> adj[MAXN];

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

int pw(int x, int p)
{
	int ret = 1;
	while(p)
	{
		if(p & 1) ret = (ret * 1ll * x) % mod;
		x = (x * 1ll * x) % mod;
		p >>= 1;
	}

	return ret;
}

int low[MAXN], disc[MAXN], dfs_time;
vector<vector<pair<int, int> > > bcc;
vector<pair<int, int> > st, bridges;

void tarjan(int u, int pr = -1)
{
	low[u] = disc[u] = ++dfs_time;

	int child_cnt = 0;
	for(int v: adj[u])
		if(v != pr)
		{
			if(disc[v] == -1)
			{
				st.push_back({u, v});
				tarjan(v, u);
				child_cnt++;
				chkmin(low[u], low[v]);

				if((pr == -1 && child_cnt > 1) || (pr != -1 && disc[u] <= low[v]))
				{
					vector<pair<int, int> > curr = {make_pair(u, v)};
					while(st.back() != make_pair(u, v))
					{
						curr.push_back(st.back());
						st.pop_back();
					}	

					st.pop_back();
					if(curr.size() == 1) bridges.push_back(curr.back());
					else bcc.push_back(curr);
				}
			}
			else if(disc[v] < disc[u])
			{
				chkmin(low[u], disc[v]);
				st.push_back({u, v});
			}
		}
}

void compute_bcc()
{
	dfs_time = 0;
	for(int i = 1; i <= n; i++) low[i] = disc[i] = -1;
	for(int i = 1; i <= n; i++)
		if(disc[i] == -1)
		{
			st.clear();
			tarjan(i);
			if(!st.empty())
			{
				if(st.size() == 1) bridges.push_back(st.back());
				else bcc.push_back(st);
				st.clear();
			}
		}	
}


int fact[MAXN], inv_fact[MAXN], inv_numb[MAXN];
int comb(int n, int k) { if(n < 0 || k < 0 || n < k) return 0; return (((fact[n] * 1ll * inv_fact[n - k]) % mod) * 1ll * inv_fact[k]) % mod; }
int pwk[MAXN];

void solve()
{
	fact[0] = 1; for(int i = 1; i <= n + m + k; i++) fact[i] = (fact[i - 1] * 1ll * i) % mod;
	inv_fact[n + m + k] = pw(fact[n + m + k], mod - 2); for(int i = n + m + k - 1; i >= 0; i--) inv_fact[i] = (inv_fact[i + 1] * 1ll * (i + 1)) % mod;
	inv_numb[0] = 1; for(int i = 1; i <= n + m + k; i++) inv_numb[i] = (inv_fact[i] * 1ll * fact[i - 1]) % mod; 
	pwk[0] = 1; for(int i = 1; i <= n + m + k; i++) pwk[i] = (pwk[i - 1] * 1ll * k) % mod;

	compute_bcc();

	int answer = 1;
	answer = (answer * 1ll * pw(k, bridges.size())) % mod;
	for(auto it: bcc)
	{
		set<int> nodes;
		for(auto e: it)
			nodes.insert(e.first), nodes.insert(e.second);

		if(nodes.size() < it.size()) answer = (answer * 1ll * comb(it.size() + k - 1, it.size())) % mod;       // BCC with more than 1 cycle
		else if(nodes.size() == it.size())      // simple cycle
		{
			int cnt = it.size(), c_ans = 0;
			for(int i = 0; i < cnt; i++)
			{
				int g = (i == 0) ? cnt : __gcd(cnt, i);  
				c_ans = (c_ans + pwk[g]) % mod;
			}

			c_ans = (c_ans * 1ll * inv_numb[cnt]) % mod;
			answer = (answer * 1ll * c_ans) % mod;
		}
	}


	cout << answer << endl;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	read();
	solve();
	return 0;
}



Measured memory_bytes: 35072