#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <queue>
#include <assert.h>
#include <set>
#include <string>
#include <string.h>
#include <stack>
#define Endl endl
#define mp make_pair
#define ll long long 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define over(A) {cout<<A<<endl;exit(0);}
#define all(A) A.begin(),A.end()
#define ceil(a,b) ((a-1)/b+1)
typedef unsigned long long ull;
const int inf=1039074182;
const int mod=1e9+7;
using namespace std;
int n,m,k;
vector <pair<int,int> > vec[55];
bool AP[55];
int disc[55];
int low[55];
stack <int> stk;
vector <vector<int> > BiComponent;
pair<int,int> edge[105];
bool visitEdge[105];

namespace combinatorics
{
	int *fac;
	int *ifac;
	int mod;
	inline int add(int a,int b)
	{
		return (a+b)%mod;
	}
	inline int minus(int a,int b)
	{
		return (a-b+mod)%mod;
	}
	inline int multiply(int a,int b)
	{
		return (1LL*a*b)%mod;
	}
	inline int fastpow(int basic,int x)
	{
		int res=1;
		while(x)
		{
			if(x&1)	res=multiply(res,basic);
			basic=multiply(basic,basic);
			x>>=1;
		}
		return res;
	}
	inline int inv(int x)
	{
		return fastpow(x,mod-2);
	}
	void init(int n,int tmod)
	{
		mod=tmod;
		fac=new int[n+5];
		ifac=new int[n+5];
		fac[0]=1;
		for(int i=1;i<=n;i++)
		{
			fac[i]=multiply(fac[i-1],i);
		}
		ifac[n]=inv(fac[n]);
		for(int i=n-1;i>=0;i--)
		{
			ifac[i]=multiply(ifac[i+1],i+1);
		}
	}
	inline int C(int n,int m)
	{
		return multiply(multiply(fac[n],ifac[m]),ifac[n-m]);
	}
	inline int Cat(int x)
	{
		return multiply(C(x*2,x),inv(x+1));
	}
};
using namespace combinatorics;

int calcS(int n)
{
	int res=fastpow(k,n);
	for(int i=1;i<n;i++)
	{
		res=add(res,fastpow(k,__gcd(i,n)));
	}
	return multiply(res,inv(n));
}

int calcC(int n)
{
	return C(n+k-1,k-1);
}

bool dfs(int x,int par=-1)
{
	static int time=0;
	low[x]=disc[x]=time++;
	int child=0;
	for(auto u:vec[x])
	{
		if(u.first==par) continue;
		if(!visitEdge[u.second]) stk.push(u.second);
		visitEdge[u.second]=true;
		if(disc[u.first]==-1)
		{
			child++;
			dfs(u.first,x);
			if((par==-1 && child>=2) || (par!=-1 && low[u.first]>=disc[x]))
			{
				AP[x]=true;
				vector <int> edge;
				while(!stk.empty())
				{
					edge.push_back(stk.top());
					stk.pop();
					if(edge.back()==u.second) break;
				}
				BiComponent.push_back(edge);
			}
			low[x]=min(low[x],low[u.first]);
		}
		else low[x]=min(low[x],disc[u.first]);
	}
}

int main()
{
//	freopen("input.txt","r",stdin);
	init(200,1e9+7);
	cin>>n>>m>>k;
//	cout<<multiply(pow(41,5),calcC(45))<<endl;
	int x,y;
	for(int i=0;i<m;i++)
	{
		scanf("%d%d",&x,&y);
		x--;
		y--;
		vec[x].push_back(mp(y,i));
		vec[y].push_back(mp(x,i));
		edge[i].first=x;
		edge[i].second=y;
	}
	memset(disc,-1,sizeof(disc));
	for(int i=0;i<n;i++)
	{
		if(disc[i]==-1)
		{
			dfs(i);
			if(stk.empty()) continue;
			vector <int> temp;
			while(!stk.empty())
			{
				temp.push_back(stk.top());
				stk.pop();
			}
			BiComponent.push_back(temp);
		}
	}
	vector <int> temp;
	int res=1;
	for(auto &x:BiComponent)
	{
		temp.clear();
		for(auto u:x)
		{
			temp.push_back(edge[u].first);
			temp.push_back(edge[u].second);
		}
		sort(all(temp));
		temp.erase(unique(all(temp)),temp.end());
//		cout<<temp.size()<<' '<<x.size()<<endl;
		if(temp.size()==x.size())
		{
			res=multiply(res,calcS((int)x.size()));
		}
		else if(x.size()==1)
		{
			res=multiply(res,k);
		}
		else
		{
			res=multiply(res,calcC((int)x.size()));
		}
	}
	cout<<res<<endl;
	return 0;
}

Measured memory_bytes: 256