#include <bits/stdc++.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using ll=long long;
using R=long double;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}


// Problem Specific Parameter:
const ll mod=1000000007LL;
ll C[310][310];
	
ll power(ll a,ll n){
	ll b=1LL;
	while(n){
		if(n&1) b=b*a%mod;
		a=a*a%mod;
		n>>=1;
	}
	return b;
}

void init(){
	rep(i,301){
		rep(j,i+1){
			if(j==0 or j==i)
				C[i][j]=1LL;
			else
				C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
		}
	}
}

ll cycle_calc(ll n,ll k){
	ll ret=0LL;
	rep(i,n){
		ret+=power(k,__gcd<ll>(n,i));
		ret%=mod;
	}
	ret=ret*power(n,mod-2)%mod;
	return ret;
}

using edge=struct{int from,to,idx;};
using G=vector<vector<edge>>;

void add_edge(G &graph,int from,int to,int idx){ 
	graph[from].push_back({from,to,idx});
	graph[to].push_back({to,from,idx});
}

auto low_link(const G& graph){
    int n=graph.size(),k=0;
    vector<int> par(n),ord(n,-1),low(n),root(n,0);

    stack<edge> s;
    vector<vector<edge>> bcomp;

    auto dfs=[&](int v,int p,int &k){
        auto func=[&](int v,int p,int &k,auto func)->void{
            ord[v]=k++,low[v]=ord[v],par[v]=p;

            for(auto &e:graph[v]){
                if(e.to==p) continue;
                if (ord[e.to] < ord[v]) s.push(e);

                if(ord[e.to]==-1){
                    func(e.to,v,k,func);
                    chmin(low[v],low[e.to]);

                     if(low[e.to] >= ord[v]) {  
						bcomp.emplace_back(vector<edge>());

						while (1){
							edge f=s.top();s.pop();
							bcomp.back().emplace_back(f);
							if(f.from == v && f.to == e.to) break;
						}
					}

                }else
                    chmin(low[v],ord[e.to]);
            }
        };
        return func(v,p,k,func);
    };

    rep(v,n) if(ord[v]==-1) dfs(v,-1,k),root[v]=1;
    return bcomp;
}



int a[110],b[110];


int main(void){
	init();

	int n,m,k;
	cin >> n >> m >> k;

	G graph(n);
	rep(i,m){
		cin >> a[i] >> b[i];
		a[i]--,b[i]--;
		add_edge(graph,a[i],b[i],i);
	}

	auto bcomp=low_link(graph);
		

	ll ans=1LL;

	for(auto &edges:bcomp){
		//cout << "Comp" << endl;
		bool cycle=true;
		const int all=edges.size();
		// rep(i,all) cout << edges[i].from << " " << edges[i].to << endl;
		rep(i,all) if(edges[i].from!=edges[(i+1)%all].to) cycle=false;

		if(cycle){
			ans*=cycle_calc(all,k);
			ans%=mod;
		}else if(all==1){
			ans*=k;
			ans%=mod;
		}else{
			ans*=C[all+k-1][k-1];
			ans%=mod;
		}
	}

	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1152