#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=210,P=1e9+7;

int c[N][N],s[N][N];

int iscut[N]; 
int bccno[N]; 
int pre[N], dfs_clock, bcc_cnt; 
vector<int> bcc[N];  
struct E{
   int f,t,xt;
}e[N*N];
stack<E> S;

int h[N],cnt;

int fac[N],ifac[N],inv[N];

void adge(int u,int v){
    e[++cnt]=(E){u,v,h[u]};h[u]=cnt;
}

inline int ksm(int a,int n){
	int ans=1;
	for(;n;n>>=1,a=(ll)a*a%P)
		if(n&1) ans=(ll)ans*a%P;
	return ans;
}

int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}

int k,n,ans=1;

inline int polya(int n){
	int ans=0;
	for(int i=1;i<=n;i++){
		ans=(ans+ksm(k,gcd(n,i)))%P;
	}
//	printf("polya ans(%d),inv=%d %d\n",n,ans,inv[n]); 
	return (ll)ans*inv[n]%P;
}

inline int C(int n,int m){
	return (ll)fac[n]*ifac[n-m]%P*ifac[m]%P;
}


int dfs(int u,int fa){
   int lowu=pre[u]=++dfs_clock;
   int child=0;
   for(int i=h[u];~i;i=e[i].xt){
       int v=e[i].t;
       E e=(E){u,v};
       if(!pre[v]){
           S.push(e);
       //    printf("push <%d,%d>\n",e.f,e.t); 
           child++;
           int lowv=dfs(v,u);
           lowu=min(lowu,lowv);
           if(lowv>=pre[u]){
               iscut[u]=true;
               bcc_cnt++; 
               int m=0;
               for(;;){
               	   m++;
            	   E x=S.top();  
				   S.pop();
                   if(bccno[x.f]!=bcc_cnt){ bcc[bcc_cnt].push_back(x.f);bccno[x.f]=bcc_cnt; }
                   if(bccno[x.t]!=bcc_cnt){ bcc[bcc_cnt].push_back(x.t);bccno[x.t]=bcc_cnt; }
                   if(x.f==u&&x.t==v) break;
               }
               int n=bcc[bcc_cnt].size();
               if(n==m){ 
			   		ans=(ll)ans*polya(n)%P;
			   }
               else if(n>m){
			  
			  	 	ans=(ll)ans*k%P;
			  	 	
			   }
               else{
               	
			   		ans=(ll)ans*C(m+k-1,k-1)%P;
			   }
               
            //   printf("|V|=%d,|E|=%d\n",bcc[bcc_cnt].size(),m); 
               
           }
       }
       else if(pre[v]<pre[u] && v!=fa){
           S.push(e);
        //   printf("push <%d,%d>\n",e.f,e.t); 
           lowu=min(lowu,pre[v]);
       }
   }
   if(fa<0&&child==1) iscut[u]=0;
   return lowu;
}
void find_bcc(int n){   
    for(int i=1;i<=n;i++)
      if(!pre[i]) dfs(i,-1);
}



int main(){
	memset(h,cnt=-1,sizeof(h));
	int m;
	scanf("%d%d%d",&n,&m,&k);
	
	inv[0]=fac[0]=ifac[0]=inv[1]=1;
	int n2=m+k;
	for(int i=1;i<=n2;i++) fac[i]=(ll)fac[i-1]*i%P;
	for(int i=2;i<=n2;i++) inv[i]=(ll)(P-P/i)*inv[P%i]%P;
	for(int i=1;i<=n2;i++) ifac[i]=(ll)ifac[i-1]*inv[i]%P; 
	
	for(int i=1;i<=m;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		adge(a,b);
		adge(b,a);
	}
//	printf("%d\n",ans); 
	
	find_bcc(n);
	
	/*for(int i=1;i<=bcc_cnt;i++){
		printf("bcc %d\n",i);
		for(int j=0;j<bcc[i].size();j++){
			printf("%d ",bcc[i][j]);
		}
		cout<<endl;
	}*/
	printf("%d\n",ans); 
	return 0;
}
/*
4 5 1
1 2
3 4
2 4
3 2
1 3

*/