#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <stack>
#define pi pair<int, int>
#define mkp make_pair
#define fi first
#define se second
#define N 202

using namespace std;

const int mod = 1e9 + 7;

struct edge{
	int to, nxt;
}e[N << 1];

int n, m, k, cnt, tot, num;
int fir[N], col[N], sze[N], szp[N], fac[N << 1], ifac[N << 1], dfn[N], low[N];

stack<pi> st;

void add(int ,int);
int gcd(int ,int);
int quick_pow(int ,int);
int C(int ,int);
void init();
void tarjan(int ,int);

int main(){
	scanf("%d%d%d", &n, &m, &k); init();
	for(int i = 1; i <= m; ++i){
		int u, v; scanf("%d%d", &u, &v);
		add(u, v); add(v, u);
	}
	for(int i = 1; i <= n; ++i)
		if(!dfn[i]) tarjan(i, 0);
	int ans = 1;
	for(int i = 1; i <= num; ++i){
		if(sze[i] == 1) ans = 1ll * ans * k % mod;
		else if(sze[i] == szp[i]){
			int tmp = 0;
			for(int j = 1; j <= sze[i]; ++j)
				(tmp += quick_pow(k, gcd(j, sze[i]))) %= mod;
			tmp = 1ll * tmp * quick_pow(sze[i], mod - 2) % mod;
			ans = 1ll * ans * tmp % mod;
		}
		else ans = 1ll * ans * C(sze[i] + k - 1, k - 1) % mod;
	}
	cout << ans << endl;
	return 0;
}

void init(){
	int lim = m + k; fac[0] = ifac[0] = 1;
	for(int i = 1; i <= lim; ++i)
		fac[i] = 1ll * fac[i - 1] * i % mod, ifac[i] = quick_pow(fac[i], mod - 2);
	return ;
}

int C(int x, int y){
	return 1ll * fac[x] * ifac[y] % mod * ifac[x - y] % mod;
}

int gcd(int x, int y){
	return !y ? x : gcd(y, x % y);
}

int quick_pow(int x, int y){
	int sum = 1;
	for(; y; y >>= 1, x = 1ll * x * x % mod)
		if(y & 1) sum = 1ll * sum * x % mod;
	return sum;
}

void add(int u, int v){
	e[++cnt] = (edge){v, fir[u]}; fir[u] = cnt;
	return ;
}

void tarjan(int u, int fa){
	dfn[u] = low[u] = ++tot;
	for(int i = fir[u]; i; i = e[i].nxt){
		int v = e[i].to; if(v == fa) continue;
		if(!dfn[v]){
			st.push(mkp(u, v)); tarjan(v, u);
			low[u] = min(low[u], low[v]);
			if(dfn[u] <= low[v]){
				int x, y; ++num;
				do{ 
					x = st.top().fi, y = st.top().se;
					++sze[num]; st.pop();
					if(col[x] != num) col[x] = num, ++szp[num];
					if(col[y] != num) col[y] = num, ++szp[num];
				}while(!st.empty() && (x != u || y != v));
			}
		}
		else if(dfn[v] < dfn[u]) st.push(mkp(u, v)), low[u] = min(low[u], dfn[v]);
	}
	return ;
}