Language: C++

//by xxj
//I love 7 sea k fall
#include<bits/stdc++.h>
using namespace std;
#define fst first
#define snd second
#define mp make_pair
#define ll long long
#define pii pair<int,int>
#define lowbit(x) x&-x
const int inf=1e9+7;
const double eps=1e-10;
const ll linf=1e18+7;
const ll hh=523;
const int mod=1e9+7;
inline int read(){
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
ll pow(ll a,int c){
	ll re=1;
	while (c){
		if (c&1){
			re=1ll*re*a%mod;
		}
		a=1ll*a*a%mod;
		c>>=1;
	}
	return re;
}
struct Edge{
	int next,to,bh;
}edge[207];
int head[207],len=0;;
void add(int x,int y,int bh){
	edge[len].next=head[x];
	edge[len].to=y;
	edge[len].bh=bh;
	head[x]=len++;
	edge[len].next=head[y];
	edge[len].to=x;
	edge[len].bh=bh;
	head[y]=len++;
}
ll ans=1;
int tot=1,cnt=0,num=0;
int dfn[57],low[57];
bool visited[207];
bool bridge[207],used[57];
ll h1[107][107],dp[107][107],hn[107][107];
ll jc[107],njc[107];
vector<int> hve[107];
bool f[107][107];
int n,m,k;
vector<int> findit;
ll calc(int e,int c){
	ll re=pow(c,e);
	for (int i=1;i<e;i++){
		re=(re+pow(c,__gcd(i,e)))%mod;
	}
	re=1ll*re*pow(e,mod-2)%mod;
	return re;
}
ll C(int i,int j){
	return 1ll*jc[j]*njc[i]%mod*njc[j-i]%mod;
}
void init(){
//	cout<<pow(3,2)<<endl;
	jc[0]=1;
	for (int i=1;i<=k;i++){
		jc[i]=1ll*jc[i-1]*i%mod;
	}
	njc[k]=pow(jc[k],mod-2);
	for (int i=k-1;i>=0;i--){
		njc[i]=1ll*njc[i+1]*(i+1)%mod;
	}
	for (int i=1;i<=m;i++){
		for (int j=1;j<=k;j++){
			h1[i][j]=calc(i,j);
		}
	}
	for (int i=1;i<=k;i++){
		dp[1][i]=i;
	}
	for (int i=1;i<=m;i++){
		dp[i][1]=1;
	}
	for (int i=2;i<=m;i++){
		for (int j=2;j<=k;j++){
			for (int z=1;;z++){
				if (i-z<j-1){
					break;
				}
				dp[i][j]=(dp[i][j]+dp[i-z][j-1])%mod;
			}
		}
	}
	for (int i=1;i<=m;i++){
		for (int j=1;j<=k;j++){
			for (int z=1;z<=j;z++){
				hn[i][j]=(hn[i][j]+1ll*C(z,j)*dp[i][z]%mod)%mod;
			}
		}
	}
}
void tarjan(int v,int p){
	dfn[v]=tot;
	hve[tot].push_back(v);
//	cout<<tot<<':'<<v+1<<endl;
	f[tot][v]=true;
	low[v]=tot++;
	for (int i=head[v];i!=-1;i=edge[i].next){
		int u=edge[i].to;
		if (!dfn[u]){
			tarjan(u,i);
			low[v]=min(low[v],low[u]);
			if (low[u]>dfn[v]){
				bridge[i]=true;
				bridge[i^1]=true;
				cnt++;
			}
		}
		else if (p==-1 || i!=(p^1)){
			low[v]=min(low[v],dfn[u]);
		}
	}
	if (!f[low[v]][v]){
		hve[low[v]].push_back(v);
//		cout<<low[v]<<':'<<v+1<<endl;
		f[low[v]][v]=true;		
	}
}
void dfs(int v,int c){
	used[v]=true;
//	cout<<v<<endl;
	for (int i=head[v];i!=-1;i=edge[i].next){
		int u=edge[i].to;
		if (!f[c][u] || visited[i]){
			continue;
		}
		num++;
		visited[i]=true;
		visited[i^1]=true;
		if (used[u]){
			cnt++;
			continue;
		}
		dfs(u,c);
	}
}
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	init();
//	cout<<h1[4][2]<<endl;
	memset(head,-1,sizeof(head));
	for (int i=0;i<m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		x--;
		y--;
		add(x,y,i);
	}
	for (int i=0;i<n;i++){
		if (!dfn[i]){
			tarjan(i,-1);
		}
	}
//	puts("");
//	for (int i=0;i<n;i++){
//		cout<<f[1][i]<<' ';
//	}
//	puts("");
	ans=pow(k,cnt);
//	cout<<cnt<<endl;
	for (int i=1;i<tot;i++){
		if (hve[i].size()==1){
			continue;
		}
		memset(used,false,sizeof(used));
		cnt=0;
		num=0;
//		puts("dfsbegin");
		dfs(hve[i][0],i);
//		cout<<cnt<<' '<<num<<endl;
//		puts("dfsend");
		if (cnt==1){
			ans=1ll*ans*h1[num][k]%mod;
		}
		else{
			ans=1ll*ans*hn[num][k]%mod;
		}
	}
	printf("%lld\n",ans);
	return 0;
}
/*
input:
*/


Compiler output:
a.cc: In function 'long long int calc(int, int)':
a.cc:61:42: error: invalid operands of types '__gnu_cxx::__promote<double>::__type' {aka 'double'} and 'const int' to binary 'operator%'
   61 |                 re=(re+pow(c,__gcd(i,e)))%mod;
      |                    ~~~~~~~~~~~~~~~~~~~~~~^~~~
      |                       |                   |
      |                       |                   const int
      |                       __gnu_cxx::__promote<double>::__type {aka double}
a.cc:63:31: error: invalid operands of types '__gnu_cxx::__promote<double>::__type' {aka 'double'} and 'const int' to binary 'operator%'
   63 |         re=1ll*re*pow(e,mod-2)%mod;
      |            ~~~~~~~~~~~~~~~~~~~^~~~
      |                  |             |
      |                  |             const int
      |                  __gnu_cxx::__promote<double>::__type {aka double}