#include<bits/stdc++.h>

using namespace std;
#define REPP(i,a,b,c) for(int i=a; i<=b; i+=c)
#define REP(i,a,b) REPP(i,a,b,1)
#define REVV(i,a,b,c) for(int i=a; i>=b; i-=c)
#define REV(i,a,b) REVV(i,a,b,1)
#define FOR(i,a) REP(i,0,(int)a-1)
#define FORD(i,a) REV(i,(int)a-1,0)
#define PB push_back
#define POB pop_back
#define MP make_pair
#define FI first
#define SE second
typedef long long ll;
typedef unsigned long long ull;
typedef pair < int , int > pii;
typedef vector < int > vi;
typedef vector < pii > vii;
typedef vector < ll > vl;

const double EPS = 1e-9;
const double PI = acos(-1);
const int INF = 1e9;
const ll MOD = 1e9 + 7;

ll addMod(ll a, ll b){
	return (a+b) % MOD;
}

ll mulMod(ll a, ll b){
	return (a*b) % MOD;
}

ll fast(ll a, ll b){
	if(b == 0) return 1;
	ll tmp = fast(a, b/2);
	tmp = mulMod(tmp, tmp);
	if(b % 2 == 1) tmp = mulMod(tmp, a);
	return tmp;
}

/////////////////////////////////////////////////////////

const int N = 100;

int cnt = 0;
int num[N + 5], low[N + 5];
bool flag[N + 5];
ll tmpVal[N + 5][N + 5], val[N + 5];
stack < int > st;
vi scc[N + 5];
int idx;
vi G[N + 5];
int n,m,k;

int tarjan(int u, int p){
	if(num[u] != -1) return num[u];
	num[u] = low[u] = ++cnt;
	st.push(u);
	for(int v : G[u]){
		if(v == p) continue;
		if(num[v] != -1){
			low[u] = min(low[u], num[v]);
		}
		else{
			low[u] = min(low[u], tarjan(v,u));
			if(num[u] <= low[v]){
				scc[idx].PB(u);
				while(!st.empty() && st.top() != v){
					scc[idx].PB(st.top());
					st.pop();
				}
				scc[idx].PB(st.top());
				st.pop();
				idx++;
			}
		}
			
	}
	return low[u];
}
ll fact[N*2 + 5];
ll combin(ll nn, ll kk){
	return mulMod(fact[nn], fast(mulMod(fact[nn-kk], fact[kk]), MOD-2));
}

void getVal(){
	fact[0] = 1;
	REP(i,1,2*N+3) fact[i] = mulMod(fact[i-1], i);
//	FOR(i,N+3) tmpVal[0][i] = 1; 
//	REP(len,1,N){
//		REP(last,1,k){
//			REP(i,1,last){
//				tmpVal[len][last] = addMod(tmpVal[len][last], tmpVal[len-1][i]);
//			}
//		}
//	}
	REP(len,1,N){
		val[len] = combin(len+k-1, k-1);
//		val[len] = tmpVal[len][k];
	}
	val[0] = 1;
}

void input(){
	cin >> n >> m >> k;
	int u,v;
	FOR(i,m){
		cin >> u >> v;
		G[u].PB(v);
		G[v].PB(u);
	}
}

void reset(){
	memset(flag,0,sizeof flag);
	memset(num,-1,sizeof num);
	while(!st.empty()) st.pop();
	idx = 0;
}

int getSize(int id){
	int ret = 0;
	memset(flag,0,sizeof flag);
	FOR(i,scc[id].size()) flag[scc[id][i]] = true;
////	printf("SCC %d contains ", id);
	FOR(i,scc[id].size()){
		int u = scc[id][i];
//		printf("%d ",u);
		FOR(j,G[u].size()){
			int v = G[u][j];
			if(flag[u] && flag[v]) ret++;
		}
	}
//	puts("");
	return ret / 2;
}

ll polya(int sz){
	ll ret = 0;
	FOR(i,sz){
		ll d = __gcd(i,sz);
		ret = addMod(ret, fast(k, d));
	}
	return mulMod(ret, fast(sz, MOD-2));
}

ll solve(){
	int ct = 0;
	ll ret = 1;
	int sz;
	FOR(i,idx){
		sz = getSize(i);
		ct += sz;
//		printf("	sz %d\n",sz);
		if(sz == scc[i].size()){
			// 1 cycle
//			printf("polya %lld\n",polya(sz));
			ret = mulMod(ret, polya(sz));
		}
		else{
			// nested
//			printf("mult %lld\n",val[sz+1]);
			ret = mulMod(ret, val[sz]);
		}
	}
//	printf("remainder edge %d\n",m-ct);
	return mulMod(ret, fast(k, m-ct));
}

int main(){
	ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	reset();
	input();
	getVal();
	REP(i,1,n) if(num[i] == -1) tarjan(i,0);
	cout << solve() << endl;
	return 0;
}

Measured memory_bytes: 256