#include<stdio.h>
#include<algorithm>
#include<vector>
#include<set>
#include<stack>
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
 
using namespace std;
typedef int Weight;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(int src, int dst, Weight weight) :
    src(src), dst(dst), weight(weight) { }
};
bool operator < (const Edge &e, const Edge &f) {
  return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
    e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
 
typedef vector<Weight> Array;
typedef vector<Array> Matrix;
struct UndirectionalCompare {
  bool operator() (const Edge& e, const Edge& f) const {
    if (min(e.src,e.dst) != min(f.src,f.dst))
      return min(e.src,e.dst) < min(f.src,f.dst);
    return max(e.src,e.dst) < max(f.src,f.dst);
  }
};
typedef set<Edge, UndirectionalCompare> Edgeset;
void visit(const Graph &g, int v, int u,
    vector<int>& art, vector<Edgeset>& bcomp,
    stack<Edge>& S, vector<int>& num, vector<int>& low, int& time) {
  low[v] = num[v] = ++time;
  FOR(e, g[v]) {
    int w = e->dst;
    if (num[w] < num[v]) S.push(*e);              // for bcomps
    if (num[w] == 0) {
      visit(g, w, v, art, bcomp, S, num, low, time);
      low[v] = min(low[v], low[w]);
      if ((num[v] == 1 && num[w] != 2) ||         // for arts
          (num[v] != 1 && low[w] >= num[v])) art.push_back(v);
      if (low[w] >= num[v]) {                     // for bcomps
        bcomp.push_back(Edgeset());
        while (1) {
          Edge f = S.top(); S.pop();
          bcomp.back().insert(f);
          if (f.src == v && f.dst == w) break;
        }
      }
    } else low[v] = min(low[v], num[w]);
  }
}
void articulationPoint(const Graph& g,
    vector<int>& art, vector<Edgeset>& bcomp) {
  const int n = g.size();
  vector<int> low(n), num(n);
  stack<Edge> S;
  REP(u, n) if (num[u] == 0) {
    int time = 0;
    visit(g, u, -1, art, bcomp, S, num, low, time);
  }
}
int gcd(int a,int b){
	while(a){
		b%=a;
		int c=a;a=b;b=c;
	}
	return b;
}
long long inv[110000];
long long fact[110000];
long long factinv[110000];
long long mod=1000000007;
long long pw(long long a,long long b){
	long long ret=1;
	while(b){
		if(b%2)ret=ret*a%mod;
		b/=2;
		a=a*a%mod;
	}
	return ret;
}
long long calc1(int a,long long b){
	long long ret=0;
	for(int i=0;i<a;i++){
		ret=(ret+pw(b,gcd(a,i+1)))%mod;
	}
	return ret*inv[a]%mod;
}
long long calc2(int a,long long b){
	return fact[a+b-1]*factinv[a]%mod*factinv[b-1]%mod;
}
Graph g;
int main(){
	
	int a,b,c;scanf("%d%d%d",&a,&b,&c);
	int M=110000;
	inv[1]=fact[0]=factinv[0]=1;
	for(int i=2;i<M;i++)inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	for(int i=1;i<M;i++)fact[i]=fact[i-1]*i%mod;
	for(int i=1;i<M;i++)factinv[i]=factinv[i-1]*inv[i]%mod;
	g=Graph(a);
	for(int i=0;i<b;i++){
		int p,q;scanf("%d%d",&p,&q);
		p--;q--;
		g[p].push_back(Edge(p,q,1));
		g[q].push_back(Edge(q,p,1));
	}
	vector<int>kt;
	vector<Edgeset>res;
	articulationPoint(g,kt,res);
	long long ret=1;
	for(int i=0;i<res.size();i++){
		Edgeset &t =res[i];
		if(t.size()==1){
			ret=ret*c%mod;
			continue;
		}
		set<int> S;
		for(Edgeset::iterator it=t.begin();it!=t.end();it++){
			S.insert((*it).src);
			S.insert((*it).dst);
		}
	//	printf("%d %d\n",S.size(),t.size());
		if(S.size()==t.size()){
			ret=ret*calc1((int)(t.size()),c)%mod;
		}else{
			ret=ret*calc2((int)(t.size()),c)%mod;
		}
	}
	printf("%lld\n",ret);
}

Measured memory_bytes: 2816