#include "bits/stdc++.h"
using namespace std;

int n;
int m;
int k;

#define MAX 52
#define MOD 1000000007

/*
set<pair<deque<int>,deque<int> > > vis;

inline void dfs(int ar, deque<int> v, deque<int> vv) {
	if (vis.count(make_pair(v, vv)))return;
	vis.insert(make_pair(v, vv));
	v.push_front(ar);
	ar = v.back();
	v.pop_back();
	dfs(ar, v, vv);
	v.push_back(ar);
	ar = v.front();
	v.pop_front();
	vv.push_front(ar);
	ar = vv.back();
	vv.pop_back();
	dfs(ar, v, vv);
	vv.push_back(ar);
	ar = vv.front();
	vv.pop_front();	
	v.push_front(vv.front());
	vv.pop_front();
	vv.push_back(v.back());
	v.pop_back();
	dfs(ar, v, vv);
}
int ar;
deque<int> v;
deque<int> vv;


int main___() {
	for (int i = 1; i <= 2; i++) {
		v.push_back(i);
	}
	for (int i = 3; i <= 4; i++) {
		vv.push_back(i);
	}
	ar = 0;
	dfs(ar, v, vv);
	return 0;
}
*/


vector<int> v[MAX];

int ord[MAX];
int lw[MAX];
int oo;
bool vis[MAX];


set<pair<int, int> > ed;

vector<vector<int> > bc;
vector<int> stk;


inline void dfs(int b,int pr=-1) {
	ord[b] = oo;
	oo++;
	lw[b] = ord[b];
	vis[b] = true;
	bool child = true;
	for (int go : v[b]) {
		if (go == pr)continue;
		if (vis[go]) {
			lw[b] = min(lw[b], ord[go]);
			ed.insert(make_pair(go, b));
			ed.insert(make_pair(b, go));
			continue;
		}
		child = false;
		int pr = stk.size();
		stk.push_back(go);
		dfs(go, b);
		lw[b] = min(lw[b], lw[go]);
		vector<int> ar;
		if (lw[go] == ord[b]) {
			while (stk.size() != pr) {
				ar.push_back(stk.back());
				stk.pop_back();
			}
		}
		if (ar.size()) {
			ar.push_back(b);
			bc.push_back(ar);
		}
		if (ord[b] >= lw[go]) {
			ed.insert(make_pair(b, go));
			ed.insert(make_pair(go, b));
		}
	}
	if (ord[b] == lw[b]) {
		stk.pop_back();
	}
}

struct UF {
	vector<int> belong;
	vector<int> size;
	void resize(int n) {
		belong.assign(n + 1, -1);
		size.assign(n + 1, 1);
	}
	inline int root(int b) {
		if (belong[b] == -1) {
			return b;
		}
		belong[b] = root(belong[b]);
		return belong[b];
	}
	void merge(int a, int b) {
		a = root(a);
		b = root(b);
		if (a == b)return;
		belong[a] = b;
		size[b] += size[a];
	}
};
UF uf;
vector<pair<int, int> > vv;

#define MAX_K 102
#define MAX_N 102

long long int dp[MAX_N][MAX_K];
long long int sum[MAX_N];

vector<int> V;
long long int pp[MAX_N];
long long int ww[MAX_K];
bool edd[MAX_N][MAX_N];
long long int ppow(long long int i, long long int j) {
	long long int res = 1LL;
	while (j) {
		if ((j & 1LL)) {
			res *= i;
			if (res >= MOD) {
				res %= MOD;
			}
		}
		j >>= 1;
		i *= i;
		if (i >= MOD) {
			i %= MOD;
		}
	}
	return res;
}

int main() {
	cin >> n >> m >> k;
	dp[0][0] = 1;
	pp[0] = 1;
	for (int i = 1; i < MAX_N; i++) {
		pp[i] = pp[i - 1];
		pp[i] *= k;
		pp[i] %= MOD;
	}
	for (int i = 0; i <=m; i++) {
		sum[i] = 0;
		for (int j = 0; j < k; j++) {
			sum[i] += dp[i][j];
			for (int jj = j; jj < k; jj++) {
				dp[i + 1][jj] += dp[i][j];
				if (dp[i + 1][jj] >= MOD)dp[i + 1][jj] %= MOD;
			}
			sum[i] %= MOD;
		}
	}
	for (int i = 0; i < m; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		a--;
		b--;
		v[a].push_back(b);
		v[b].push_back(a);
		vv.push_back(make_pair(a, b));
		edd[a][b] = true;
		edd[b][a] = true;

	}
	for (int i = 0; i < n; i++) {
		stk.push_back(i);
		if(vis[i]==false)dfs(i);
		stk.clear();
	}
	uf.resize(n);
	for (int i = 0; i < bc.size(); i++) {
		for (int j = 0; j < bc[i].size(); j++) {
			uf.merge(bc[i][0], bc[i][j]);
		}
	}
	long long int way = 1;
	for (auto it : vv) {
		if (ed.count(it)==0) {
			way *= k;
			if (way >= MOD)way %= MOD;
		}
	}
	for (int i1 = 0; i1 < bc.size(); i1++) {
		int eds = 0;
		int node = bc[i1].size();
		for (int j = 0; j < bc[i1].size(); j++) {
			for (int k = j + 1; k < bc[i1].size(); k++) {
				if (edd[bc[i1][j]][bc[i1][k]]) {
					eds++;
				}
			}
		}
		if (node == eds) {
			V.clear();
			for (int i = 1; i*i <= node; i++) {
				if (node%i == 0) {
					V.push_back(i);
					if (i*i != node)V.push_back(node / i);
				}
			}
			sort(V.begin(), V.end());
			long long int su = 0;
			for (int j = 0; j < V.size(); j++) {
				long long int way2 = pp[V[j]];
				for (int k = 0; k < j; k++) {
					if (V[j] % V[k] == 0) {
						way2 += MOD;
						way2 -= ww[k];
						if (way2 >= MOD)way2 %= MOD;
					}
				}
				ww[j] = way2;
				su += (way2 *ppow(V[j],MOD-2))%MOD;
				if (su >= MOD)su %= MOD;
			}
			way *= su;
			way %= MOD;
		}
		else {
			way *= sum[eds];
			way %= MOD;
		}
	}
	if (way < 0) {
		return 1;
	}
	printf("%lld\n", way);
	return 0;
}

Measured memory_bytes: 384