/*----------------by syr----------------*/
/*

         iii                  ii
     rBQBBBBBBE       BBR iBBBBQBBL     XBBBBBBQBBBBB
   iBBQJ    7BBB      BBsSBBr   BBQ      i      cBBB
  rBBU       iBBw     BBBQi     HBBi           KBBi
  BBH         BB5    iBBB       isL          wBB5
 GBB         iBBi    6BB                   iBBB
 BBQ         BQB     BBD                  QBBi
 BBB        BQB     iQBi                1BBv
 sBBg     wBBB      QBB               iBBB
  7BBBBBBBBBi       BBR              wBBBBBBBBBBBBB
     irvi           ii               ii    i i iii
                i5U
               BBB
               BB7
              1BB
      iPBBBBBKBBR    JBR1       rQBO   BR  UBQP  iBBQi
    7BBBGs7sXBBBi     QBBr     gBBE   rBB BB2BB7HBZQBB
   QBBi      sBQ       BBB   iBBB     SQBBR  BBBB  cBQ
  gBQ        BBg        BBB KBBi      MBBH   BBB   BBs
 iBBv       iBBi         QBBBL        BBR   pBB   iBB
 pBB        BBB         iBBBB        iBB    BBL   KBB
 MBB       BBBR        BBB JBBi      DBR   iBQ    BBL
 GBB     7BBBB2      PBBH   BBBi     BQr   DBB   iBB
  BQBXwgBBP BB7    1BBB      BBQ7   1BB    BBc   BBB
   2BBBBw   BB    EBBS        QBBi  HBa   iBB    BB7
*/
#include<bits/stdc++.h>

using namespace std;

#define PH push
#define MP make_pair
#define PB push_back
#define fst first
#define snd second
#define FOR(i, x, y) for(int i = (x); i < (y); ++i)
#define REP(i, x, y) for(int i = (x); i <= (y); ++i)
#define x0 x0123456789
#define y0 y0123456789
#define x1 x1234567890
#define y1 y1234567890
#define x2 x2345678901
#define y2 y2345678901
typedef double db;
typedef long long ll;
typedef long double ldb;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int INF = 1e9 + 7;
const int maxn = 205;

int n, m, k, col = 0;
int sim[maxn], edg[maxn], beg[maxn], bel[maxn], ver[maxn], mu[maxn];
ll ans = 1;
ll f[maxn], h[maxn], pw[maxn], dp[maxn][maxn], sum[maxn][maxn];
vector<int> g[maxn];

int qpow(ll x, ll y){
	ll ret = 1;
	for(; y; y >>= 1){
		if(y & 1) (ret *= x) %= INF;
		(x *= x) %= INF;
	}
	return ret;
}

namespace Tarjan{
	int clk = 0, top = 0, tot = 0;
	int low[maxn], dfn[maxn], stk[maxn];
	int have[maxn][maxn];
	void tarjan(int u, int fa){
		//printf("u = %d fa = %d\n", u, fa);
		low[u] = dfn[u] = ++clk;
		stk[++top] = u;
		FOR(i, 0, g[u].size()){
			int v = g[u][i];
			if(v == fa) continue;
			//printf("u = %d v = %d\n", u, v);
			if(dfn[v]) low[u] = min(low[u], dfn[v]);
			else{
				tarjan(v, u);
				low[u] = min(low[u], low[v]);
				if(low[v] >= dfn[u]){
					//printf("v = %d\n", v);
					beg[col] = tot;
					for(; stk[top + 1] != v; --top) /*printf("%d ", stk[top]), */ver[tot++] = stk[top], have[stk[top]][col] = true;
					//printf("%d\n", stk[top]);
					ver[tot++] = u;
					have[u][col] = true;
					++col;
				}
			}
		}
		//printf("u = %d low = %d dfn = %d\n", u, low[u], dfn[u]);
		return;
	}
	void work(){
		FOR(i, 0, n) if(!dfn[i]) tarjan(i, -1);
		beg[col] = tot;
		//printf("col = %d tot = %d\n", col, tot);
		//FOR(c, 0, col) printf("%d ", beg[c]);
		//puts("");
		FOR(c, 0, col){
			sim[c] = true;
			if(beg[c] + 2 == beg[c + 1]){
				(ans *= k) %= INF;
				//printf("ans = %lld\n", ans);
				continue;
			}
			FOR(i, beg[c], beg[c + 1]){
				int u = ver[i];
				int e = 0;
				FOR(j, 0, g[u].size()){
					int v = g[u][j];
					//printf("u = %d v = %d\n", u, v);
					if(have[v][c]) ++e;
				}
				//printf("u = %d e = %d\n", u, e);
				edg[c] += e;
				sim[c] &= (e == 2);
			}
		}
		return;
	}
}

int main(){
	scanf("%d%d%d", &n, &m, &k);
	pw[0] = 1;
	REP(i, 1, m) pw[i] = pw[i - 1] * k % INF;
	FOR(i, 0, m){
		int u, v; scanf("%d%d", &u, &v); --u, --v;
		g[u].PB(v);
		g[v].PB(u);
	}
	Tarjan::work();
	mu[1] = 1;
	REP(i, 2, m){
		int cnt = 0;
		bool f = false;
		int tmp = i;
		FOR(j, 2, tmp) if(!(tmp % j)){
			tmp /= j; ++cnt;
			for(; !(tmp % j); tmp /= j) f = true;
		}
		if(tmp > 1) ++cnt;
		if(f) mu[i] = 0;
		else{
			if(cnt & 1) mu[i] = -1;
			else mu[i] = 1;
		}
	}
	//FOR(c, 0, col) printf("%d %d\n", sim[c], edg[c]);
	//REP(i, 1, m) printf("%d ", mu[i]);
	//puts("");
	REP(i, 1, m){
		REP(j, 1, i) if(!(i % j))
			(f[i] += (mu[i / j] * pw[j] + INF) % INF) %= INF;
		(f[i] *= qpow(i, INF - 2)) %= INF;
		//printf("i = %d f = %lld\n", i, f[i]);
	}
	REP(i, 1, m){
		REP(j, 1, i) if(!(i % j)){
			(h[i] += f[j]) %= INF;
		}
	}
/*	REP(i, 1, m) printf("%lld ", f[i]);
	puts("");
	REP(i, 1, m) printf("%lld ", h[i]);
	puts("");
*/	dp[0][0] = 1;
	REP(i, 0, k) REP(j, 0, m){
		if(i) dp[i][j] = sum[i - 1][j];
		sum[i][j] = ((j ? sum[i][j - 1] : 0) + dp[i][j]) % INF;
	}
	FOR(c, 0, col) if(beg[c] + 2 != beg[c + 1]){
		edg[c] /= 2;
		if(!sim[c]){
/*			FOR(i, beg[c], beg[c + 1]) printf("%d ", ver[i]);
			puts("");
			FOR(i, beg[c], beg[c + 1]){
				int u = ver[i];
				FOR(j, 0, g[u].size()) printf("%d %d\n", u, g[u][j]);
			}
*/			//printf("edg = %d dp = %lld\n", edg[c], dp[k][edg[c]]);
			(ans *= dp[k][edg[c]]) %= INF;
		}
		else{
			//printf("edg = %d h = %lld\n", edg[c], h[edg[c]]);
			(ans *= h[edg[c]]) %= INF;
		}
	}
	printf("%lld\n", ans);
	return 0;
}



Measured memory_bytes: 640