#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

#define File(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
const int N = 55, M = 105;

const int mod = 1000000007;
inline int add(int x, int y){return x+y>=mod ? x+y-mod : x+y;}
inline int sub(int x, int y){return x-y<0 ? x-y+mod : x-y;}
inline int mul(int x, int y){return 1LL * x * y % mod;}
inline void inc(int &x, int y=1){x = x+y>=mod ? x+y-mod : x+y;}
inline void dec(int &x, int y=1){x = x-y<0 ? x-y+mod : x-y;}
inline int power(int x, int y){
	int res = 1;
	for(; y; y>>=1, x = mul(x, x)) if(y & 1) res = mul(res, x);
	return res;
}
inline int inv(int x){return power(x, mod - 2);}

vector<int> G[N];
int dfn[N], low[N], idx = 0;
int stke[M], tope = 0, eid = 0;
int stkv[M], topv = 0;
int n, m, k, res = 1;

int C[M*2][M*2];
void preC(int n){
	C[0][0] = 1;
	for(int i=1; i<=n; i++){
		C[i][0] = 1;
		for(int j=1; j<=i; j++)
			C[i][j] = add(C[i-1][j], C[i-1][j-1]);
	}
}

int gcd(int x, int y){
	int t;
	while(y) t = x, x = y, y = t % y;
	return x;
}

void dfs(int x, int fa){
	dfn[x] = low[x] = ++idx;
	stkv[++topv] = x;
	for(int v : G[x]){
		if(!dfn[v]){
			stke[++tope] = ++eid;
			int eidNow = eid;
			dfs(v, x);
			low[x] = min(low[x], low[v]);
			if(low[v] >= dfn[x]){
				int ce = 0, cv = 0;
				while(stke[tope] != eidNow) --tope, ++ce;
				--tope; ++ce;
				while(stkv[topv] != v) --topv, ++cv;
				--topv; cv += 2;
				if(ce == 1) res = mul(res, k);
				else if(ce == cv){
					int sum = 0;
					for(int i=0; i<cv; i++)
						inc(sum, power(k, gcd(i, cv)));
					res = mul(res, mul(sum, inv(cv)));
				}
				else res = mul(res, C[ce + k - 1][k - 1]);
			}
		}
		else if(v != fa && dfn[v] < dfn[x]){
			low[x] = min(low[x], dfn[v]);
			stke[++tope] = ++eid;
		}
	}
}

int main(){
	scanf("%d%d%d", &n, &m, &k);
	preC(m + k);
	for(int i=1; i<=m; i++){
		int u, v; scanf("%d%d", &u, &v);
		G[u].push_back(v); G[v].push_back(u);
	}
	for(int i=1; i<=n; i++)
		if(!dfn[i]) dfs(i, i);
	printf("%d\n", res);
	return 0;
}