#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 105
#define M 205
#define ll long long
#define mod 1000000007
void Read(int &p)
{
	p = 0;
	int c = getchar();
	for (; c < '0' || c > '9'; c = getchar());
	for (; c >= '0' && c <= '9'; c = getchar())p = p * 10 + c - '0';
}
int n, m, k, ans, tp, tim;
int inv[M << 1], fac[M << 1], rev[N << 1], pw[M << 1];
int dfn[N], low[N], s[M], hh[M], ss[M << 1];
int tar[M << 1], nex[M << 1], fir[N], tot = 1;
int gcd(int a, int b){return b ? gcd(b, a % b) : a;}
void Add(int x, int y)
{
	++tot;
	tar[tot] = y;
	nex[tot] = fir[x];
	fir[x] = tot;
}
void Sum(int &x, int y)
{
	x += y;
	if (x >= mod)
		x -= mod;
}
int Pow(int a, int k)
{
	if (!k)
		return 1;
	int p = Pow(a, k / 2);
	if (k & 1)
		return (ll)p * p % mod * a % mod;
	return (ll)p * p % mod;
}
int C(int n, int m)
{
	if (n < m)
		return 0;
	return (ll)fac[n] * inv[m] % mod * inv[n - m] % mod;
}
void Dfs(int x, int fa = 0)
{
    dfn[x] = low[x] = ++tim;
    for (int i = fir[x]; i; i = nex[i])
	{
		int y = tar[i];
		if (y != fa)
		{
		    if (!dfn[y])
		    {
		        s[++tp] = i >> 1;
			    Dfs(y, x);
			    low[x] = min(low[x], low[y]);
		        if (low[y] >= dfn[x])
		        {
		            hh[0] = 0;
		            while (1)
		            {
		                int z = s[tp--];
		                hh[++hh[0]] = z;
		                if (z == i >> 1)
		                	break;
		            }
		            if (hh[0] == 1)
		            {
		            	ans = (ll)ans * k % mod;
		            	continue;
		            }
					ss[0] = 0;
		            for (int i = 1; i <= hh[0]; i++)
		            {
		            	ss[++ss[0]] = tar[hh[i] << 1];
		            	ss[++ss[0]] = tar[hh[i] << 1 | 1];
					}
		            sort(ss + 1, ss + ss[0] + 1);
		            ss[0] = unique(ss + 1, ss + ss[0] + 1) - ss - 1;
		            if (ss[0] != hh[0])
		            {
		            	ans = (ll)ans * C(hh[0] + k - 1, k - 1) % mod;
		            	continue;
		            }
		            int cnt = 0;
				    for (int i = 0; i < hh[0]; ++i) 
				        Sum(cnt, pw[gcd(i, hh[0])]);
					ans = (ll)ans * cnt % mod * rev[hh[0]] % mod;
				}
		    }
		    else
		    {
		    	low[x] = min(low[x], dfn[y]);
		    	if (dfn[y] < dfn[x])
		    		s[++tp] = i >> 1;
			}
		}
	}
}
int main()
{
	fac[0] = 1;
	for (int i = 1; i <= 200; i++)
		fac[i] = (ll)fac[i - 1] * i % mod;
	inv[200] = Pow(fac[200], mod - 2);
	for (int i = 200; i >= 1; i--)
		inv[i - 1] = (ll)inv[i] * i % mod;
	rev[1] = 1;
	for (int i = 2; i <= 200; i++)
		rev[i] = (ll)(mod - mod / i) * rev[mod % i] % mod;
	Read(n), Read(m), Read(k);
    for (int i = 1; i <= m; i++) 
	{
		int x, y;
		Read(x), Read(y);
		Add(x, y), Add(y, x);
	}
	pw[0] = 1;
	for (int i = 1; i <= 200; i++)
    	pw[i] = (ll)pw[i - 1] * k % mod;
    ans = 1;
    for (int i = 1; i <= n; i++)
		if (!dfn[i])
			Dfs(i);
    printf("%d\n", ans);
}
//