#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
#define SIZE 200000//頂点数
class GRAPH
{
public:
	int num;//頂点数
	vector<int>pat[SIZE];
	vector<int>rev[SIZE];
	vector<int>etype[SIZE];//1:木辺 2:木辺の逆辺 -1:後退辺 -2:後退辺の逆辺 自己ループ非対応
	int ord[SIZE];
	int low[SIZE];
	int ordpt;
	bool flag[SIZE];
	bool isroot[SIZE];
	void undirectedadde(int s, int t)//s-t無向辺を追加
	{
		pat[s].push_back(t);
		pat[t].push_back(s);
		rev[s].push_back(pat[t].size() - 1);
		rev[t].push_back(pat[s].size() - 1);
		etype[s].push_back(0);
		etype[t].push_back(0);
	}
	void lowdfs(int node)
	{
		if (flag[node])return;
		flag[node] = true;
		ord[node] = ordpt++;
		for (int i = 0; i < pat[node].size(); i++)
		{
			if (!flag[pat[node][i]])
			{
				etype[node][i] = 1;
				etype[pat[node][i]][rev[node][i]] = 2;
				lowdfs(pat[node][i]);
			}
			else
			{
				if (etype[node][i] == 0)
				{
					etype[node][i] = -1;
					etype[pat[node][i]][rev[node][i]] = -2;
				}
			}
		}
	}
	void lowcalc(int node)
	{
		low[node] = ord[node];
		for (int i = 0; i < pat[node].size(); i++)
		{
			if (etype[node][i] == 1)
			{
				lowcalc(pat[node][i]);
				low[node] = min(low[node], low[pat[node][i]]);
			}
			if (etype[node][i] == -1)
			{
				low[node] = min(low[node], ord[pat[node][i]]);
			}
		}
	}
	bool isbridge(int node, int k)//node-pat[node][k]が橋かどうか
	{
		if (etype[node][k] <= 0)return false;
		if (etype[node][k] == 2)
		{
			int t = pat[node][k];
			k = rev[node][k];
			node = t;
		}
		if (low[pat[node][k]] > ord[node])return true;
		else return false;
	}
	bool isartic(int node)//nodeが関節点かどうか
	{
		if (isroot[node])
		{
			int cnt = 0;
			for (int i = 0; i < pat[node].size(); i++)if (etype[node][i] == 1)cnt++;
			if (cnt >= 2)return true;
			else return false;
		}
		else
		{
			for (int i = 0; i < pat[node].size(); i++)
			{
				if (etype[node][i] == 1)
				{
					if (low[pat[node][i]] >= ord[node])return true;
				}
			}
			return false;
		}
	}
	int tpt;
	int nv[SIZE], ne[SIZE];
	void dfs(int node, int c)
	{
		if (isroot[node])
		{
			int cnt = 0;
			for (int i = 0; i < pat[node].size(); i++)
			{
				if (etype[node][i] == 1)
				{
					tpt++;
					ne[tpt - 1]++;
					nv[tpt - 1]++;
					dfs(pat[node][i], tpt - 1);
				}
			}
		}
		else
		{
			nv[c]++;
			for (int i = 0; i < pat[node].size(); i++)
			{
				if (etype[node][i] == 1)
				{
					if (low[pat[node][i]] >= ord[node])
					{
						tpt++;
						ne[tpt - 1]++;
						nv[tpt - 1]++;
						dfs(pat[node][i], tpt - 1);
					}
					else ne[c]++, dfs(pat[node][i], c);
				}
				else if (etype[node][i] == -1)ne[c]++;
			}
		}
	}
};
GRAPH gr;
typedef long long ll;
ll mod = 1000000007;
ll inv[SIZE + 1];
ll kai[SIZE + 1];
ll invkai[SIZE + 1];
void invinit()
{
	inv[1] = 1;
	for (int i = 2; i <= SIZE; i++)
	{
		inv[i] = mod - (mod / i)*inv[mod%i] % mod;
	}
	kai[0] = invkai[0] = 1;
	for (int i = 1; i <= SIZE; i++)
	{
		kai[i] = kai[i - 1] * i%mod;
		invkai[i] = invkai[i - 1] * inv[i] % mod;
	}
}
ll com(ll a, ll b)
{
	if (b < 0 || a < b)return 0;
	return (invkai[b] * invkai[a - b]) % mod*kai[a] % mod;
}
ll po(ll a, ll b)
{
	if (b == 0)return 1;
	ll z = po(a, b / 2);
	z = z*z%mod;
	if (b & 1)z = z*a%mod;
	return z;
}
ll gcd(ll a, ll b)
{
	for (;;)
	{
		if (a < b)swap(a, b);
		a %= b;
		if (a == 0)return b;
	}
}
int main()
{
	int num, way, col;
	scanf("%d%d%d", &num, &way, &col);
	for (int i = 0; i < way; i++)
	{
		int za, zb;
		scanf("%d%d", &za, &zb);
		za--, zb--;
		gr.undirectedadde(za, zb);
	}
	invinit();
	gr.tpt = 0;
	for (int i = 0; i < num; i++)
	{
		if (gr.flag[i])continue;
		gr.isroot[i] = true;
		gr.lowdfs(i);
		gr.lowcalc(i);
		gr.dfs(i, -1);
		gr.tpt++;
	}
	ll ans = 1;
	for (int p = 0; p < gr.tpt; p++)
	{
		if (gr.ne[p] == 0)continue;
		int a = gr.nv[p], b = gr.ne[p];
		//printf("%d %d\n", a, b);
		if (a > b)ans = ans*col%mod;
		else if (a == b)
		{
			ll s = 0;
			for (int i = 1; i <= a; i++)
			{
				ll g = gcd(i, a);
				s += po(col, g);
			}
			s = s%mod*inv[a] % mod;
			ans = ans*s%mod;
		}
		else ans = ans*com(b + col - 1, col - 1) % mod;
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 20736