#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<cstdio>
#include<cmath>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))

const int INF=1000000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};

struct UF{
	int par[102],r[102],siz[102];
	void init(){
		rep(i,102){
			par[i] = i;
			r[i] = 0;
			siz[i] = 1;
		}
	}
	int find(int x){
		if(par[x] == x)return x;
		return par[x] = find(par[x]);
	}
	bool same(int x,int y){
		return find(x) == find(y);
	}
	void unit(int x,int y){
		if(same(x,y))return;
		x = find(x);
		y = find(y);
		if(r[x] < r[y]){
			par[x] = y;
			siz[y] += siz[x];
		}
		else {
			par[y] = x;
			siz[x] += siz[y];
			if(r[x] == r[y]){
				r[x] ++;
			}
		}
	}
}uf;

const ll M = 1000000007;

ll modpow(ll x,ll k){
	if(k == 0)return 1;
	ll ret = modpow(x,k/2);
	ret *= ret; ret %= M;
	if(k%2 == 1){ ret *= x; ret %= M; }
	return ret;
}

ll inverse(ll x){
	return modpow(x,M-2);
}

ll C(ll n,ll k){
	ll ret = 1;
	rep1(i,k){
		ret *= n+1-i; ret %= M;
		ret *= inverse(i); ret %= M;
	}
	return ret;
}

vector<P> G[102];
int color[102];
bool dfs(int v,int c){
	if(color[v] == c)return true;
	if(color[v] == 0)return true;
	if(color[v] != -1)return false;
	color[v] = c;
	rep(i,G[v].size()){
		if(!dfs(G[v][i].fr,c))return false;;
	}
	return true;
}
bool same(int s,int t,int u){
	rep(i,102)color[i] = -1;
	color[s] = 0;
	dfs(t,1);
	return dfs(u,2);
}

int main(){
	ll n,m,k;
	ll a[102],b[102];
	scanf("%lld%lld%lld",&n,&m,&k);
	rep(i,m){
		scanf("%lld%lld",&a[i],&b[i]);
		G[a[i]].pb(P(b[i],i));
		G[b[i]].pb(P(a[i],i));
	}
	
	ll f[52],g[52];
	rep1(i,n){
		f[i] = modpow(k,i);
		rep1(d,i-1){
			if(i%d == 0)f[i] += M-f[d];
		}
		f[i] %= M;
		g[i] = 0;
		rep1(d,i){
			if(i%d == 0)g[i] += f[d]*inverse(d);
		}
		g[i] %= M;
		//cout << i << ":" << f[i] << " " << g[i] << endl;
	}
	
	uf.init();
	rep1(i,n){
		for(int j = 0 ; j < G[i].size() ; j ++){
			for(int t = j+1 ; t < G[i].size() ; t ++){
				if(!same(i,G[i][j].fr,G[i][t].fr)){
					uf.unit(G[i][j].sc,G[i][t].sc);
					//printf("%d %lld %lld\n",i,G[i][j].fr,G[i][j].sc);
					//printf("%lld %lld\n",G[i][j].sc,G[i][t].sc);
				}
			}
		}
	}
	
	/*rep(i,m){
		cout << i << ":" << uf.find(i) << endl;
	}*/
	
	ll ret = 1;
	ll used = 0;
	rep(i,m){
		if(uf.find(i) != i)continue;
		if(uf.siz[i] == 1){
			ret *= k;
			ret %= M;
			continue;
		}
		set<ll> cnt;
		rep(j,m){
			if(uf.same(i,j)){
				//cout << i << " " << j << endl;
				//cout << uf.find(i) << " " << uf.find(j) << endl;
				cnt.insert(a[j]);
				cnt.insert(b[j]);
			}
		}
		if(cnt.size() == uf.siz[i])ret *= g[cnt.size()];
		else ret *= C(k+uf.siz[i]-1,k-1);
		used += cnt.size();
		ret %= M;
		//cout << i << ":" << cnt.size() << " " << ret << endl;
	}
	//rep(i,m-used){ ret *= k; ret %= M; }
	cout << ret << endl;
}



Measured memory_bytes: 256