题意：
染色图是无向完全图，且每条边可被染成k种颜色中的一种。
两个染色图是同构的，当且仅当可以改变一个图的顶点的编号，使得两个染色图完全相同。
问N个顶点，k种颜色，本质不同的染色图个数（模质数N≤53，P<109）。
想了一节课和一中午又看了课件
相同类型的循环合并的想法很巧妙
首先，点的置换对应唯一边的置换，我们可以枚举所有点的置换，找出每个置换下边置换的循环有多少个，然后套$Polya$公式
但是复杂度带叹号
我们发现，很多点置换类型是一样的，我们可以对$n$搜索划分来枚举点置换的类型(即每个循环的长度)，然后找出这种类型的置换有多少个
设每个循环长度$L_1,L_2,...,L_n$，那么相同类型的置换就相当于每个循环做圆排列，然后消除循环长度相同的影响
$\frac{n!}{L_1 L_2...L_n s_1! s_2!...s_t!}$
$s$为相同的长度的个数
那么如何从点的置换得到边的置换？
同一个循环里的边，他们的循环个数为$\frac{L}{2}$，具体可以把点排成一个圈画图观察一下
两个循环之间的边，他们的循环长度为$LCM(L_1,L_2)$，共有$L_1*L_2$条边，则个数为$GCD(L_1,L_2)$
然后就可以做了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=;
typedef long long ll;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return x*f;
}
int n,m,P;
ll inv[N],fac[N],facInv[N];
void ini(){
inv[]=;fac[]=facInv[]=;
for(int i=;i<=n;i++){
if(i!=) inv[i]=-P/i*inv[P%i]%P;
if(inv[i]<) inv[i]+=P;
fac[i]=fac[i-]*i%P;
facInv[i]=facInv[i-]*inv[i]%P;
}
}
int L[N],tot;
ll sum,ans;
inline int gcd(int a,int b){return b== ? a : gcd(b,a%b);}
inline ll Pow(ll a,int b){
ll re=;
for(;b;b>>=,a=a*a%P)
if(b&) re=re*a%P;
return re;
}
inline void mod(ll &x){if(x>=P) x-=P;}
void dfs(int d,int now){
if(d==n){
int lo=;
ll cnt=fac[n],same=;
sort(L+,L++tot);
//printf("tot %d\n",tot);
//for(int i=1;i<=tot;i++) printf("%d ",L[i]);puts("\n end");
for(int i=;i<=tot;i++){
lo+=L[i]/;
for(int j=i+;j<=tot;j++) lo+=gcd(L[i],L[j]); cnt=cnt*inv[L[i]]%P;
if(i!=&&L[i]==L[i-]) same++;
else if(same!=) cnt=cnt*facInv[same]%P,same=;
}
if(same!=) cnt=cnt*facInv[same]%P;
//printf("hi %d %lld\n",lo,cnt);
mod(sum+=cnt);
mod(ans+=cnt%P*Pow(m,lo)%P);
//puts("\n");
}else{
for(int j=now;d+j<=n;j++){
L[++tot]=j;
dfs(d+j,j);
tot--;
}
}
}
int main(){
freopen("in","r",stdin);
n=read();m=read();P=read();
ini();
dfs(,);
//printf("%lld %lld\n",ans,sum);
ans=ans*Pow(sum,P-)%P;
printf("%lld",ans);
}