#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#define SIZE 200005
#define MOD 1000000007

using namespace std;
typedef long long int ll;

ll inv[SIZE],fac[SIZE],finv[SIZE];
void make()
{
	fac[0]=fac[1]=1;
	finv[0]=finv[1]=1;
	inv[1]=1;
	for(int i=2;i<SIZE;i++)
	{
		inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
		fac[i]=fac[i-1]*(ll) i%MOD;
		finv[i]=finv[i-1]*inv[i]%MOD;
	}
}
ll C(int a,int b)
{
	if(a<b) return 0;
	return fac[a]*(finv[b]*finv[a-b]%MOD)%MOD;
}
int gcd(int x,int y)
{
	if(x==0) return y;
	return gcd(y%x,x);
}
ll mpow(ll m,ll t)
{
	if(t==0) return 1;
	ll ret=mpow(m*m%MOD,t/2);
	if(t%2==1) ret=ret*m%MOD;
	return ret;
}
struct UF
{
	int par[SIZE],rank[SIZE];
	
	void init(int n)
	{
		for(int i=0;i<n;i++)
		{
			par[i]=i;
			rank[i]=1;
		}
	}
	int find(int x)
	{
		if(x==par[x]) return x;
		return par[x]=find(par[x]);
	}
	void unite(int x,int y)
	{
		x=find(x);
		y=find(y);
		if(x==y) return;
		if(rank[x]<rank[y])
		{
			par[x]=y;
		}
		else
		{
			par[y]=x;
			if(rank[x]==rank[y]) rank[x]++;
		}
	}
	bool same(int x,int y)
	{
		return find(x)==find(y);
	}
};
UF uf;
vector <int> memo[SIZE];
int left[SIZE],right[SIZE];
bool now[SIZE];
struct edge
{
	int to,id;
	edge(int to=0,int id=0):to(to),id(id){}
};
vector <edge> vec[SIZE];
vector <int> can[SIZE];
int low[SIZE],ord[SIZE];
int par[SIZE],back[SIZE];
bool use[SIZE];
int now_id;
int n,m,K;

void dfs(int v,int p,int q)
{
	use[v]=true;
	par[v]=p;
	back[v]=q;
	low[v]=ord[v]=now_id++;
	for(int i=0;i<vec[v].size();i++)
	{
		edge e=vec[v][i];
		if(e.to!=p)
		{
			if(!use[e.to])
			{
				dfs(e.to,v,e.id);
				low[v]=min(low[v],low[e.to]);
			}
			else
			{
				low[v]=min(low[v],ord[e.to]);
			}
		}
	}
}
void build()
{
	for(int i=0;i<n;i++)
	{
		if(!use[i])
		{
			dfs(i,-1,-1);
		}
	}
	for(int i=0;i<n;i++)
	{
		if(par[i]==-1) continue;
		for(int j=0;j<vec[i].size();j++)
		{
			edge e=vec[i][j];
			if(e.to!=par[i]&&low[e.to]<=ord[par[i]])
			{
				can[back[i]].push_back(e.id);
				can[e.id].push_back(back[i]);
				//printf("* %d %d\n",back[i],e.id);
			}
		}
	}
}
int main()
{
	make();
	scanf("%d %d %d",&n,&m,&K);
	for(int i=0;i<m;i++)
	{
		int a,b;
		scanf("%d %d",&a,&b);a--;b--;
		vec[a].push_back(edge(b,i));
		vec[b].push_back(edge(a,i));
		left[i]=a,right[i]=b;
	}
	build();
	uf.init(m+2);
	for(int i=0;i<m;i++)
	{
		for(int j=0;j<can[i].size();j++)
		{
			uf.unite(i,can[i][j]);
		}
	}
	for(int i=0;i<m;i++) memo[uf.find(i)].push_back(i);
	ll ret=1;
	for(int i=0;i<m;i++)
	{
		if(memo[i].size()==0) continue;
		int nd=0,cnt=memo[i].size();
		for(int j=0;j<memo[i].size();j++)
		{
			int p=memo[i][j];
			if(!now[left[p]]) nd++;
			if(!now[right[p]]) nd++;
			now[left[p]]=now[right[p]]=true;
		}
		for(int j=0;j<memo[i].size();j++)
		{
			int p=memo[i][j];
			now[left[p]]=now[right[p]]=false;
		}
		//printf("%d %d\n",nd,cnt);
		if(cnt==1) ret=ret*(ll) K%MOD;
		else
		{
			if(nd<cnt)
			{
				ret=ret*C(cnt+K-1,K-1)%MOD;
			}
			else
			{
				ll all=0;
				for(int j=1;j<=nd;j++)
				{
					all+=mpow(K,gcd(j,nd));
					if(all>=MOD) all-=MOD;
				}
				all=all*inv[nd]%MOD;
				ret=ret*all%MOD;
			}
		}
	}
	printf("%lld\n",ret);
	return 0;
}


Measured memory_bytes: 19200