Description：

给出一个完全图和 $c$ 种颜色，问有多少种本质不同（交换点后还不同）的上颜色的方式。

$1\leqslant n\leqslant 53$

Solution：

首先看上去就很像 $polya$ 定理求置换群的染色方案数，根据 $polya$ 定理，有： $$ ans=\frac 1{|G|}\sum_{i=1}^{|G|} c^{m(i)} $$ 其中 $G$ 是置换群， $m(i)$ 是置换的循环节个数。

但是这题却并没有那么简单，因为它的置换是点的置换，但是却是对边染色，也就是说 $m(i)$ 是这个点置换对应的边置换的循环节数。考虑用循环来表示置换，设一个点置换为 $(a_1,a_2,\dots,a_{l_a})(b_1,b_2,\dots,b_{l_b})\cdots$ ，考虑怎么计算它对应的边循环的循环节个数。

先计算两个循环之间的，形如： $((a_1,b_1),(a_2,b_2),\dots)$ ，这个可能包含了很多循环节，每个循环节长度是 $\text{lcm}(l_a,l_b)$ ，总共有 $l_a\times l_b$ 个边，因此两个循环之间的循环节个数为 $\frac{l_a\times l_b}{\text{lcm}(l_a,l_b)}=\gcd(l_a,l_b)$ 。

在考虑一个点循环内部产生的边循环的个数，考虑 $l$ 个点围成的一个环，由于是循环所以每次置换环转动一格，如果是奇数的话显然只有转一周才会和原来重合，每个循环节长度是 $l$ ，总共有 $\frac {l(l-1)}2$ 条边，因此循环节个数为 $\frac{l-1}2$ 。如果是偶数的话要稍微麻烦一点，因为有两种边，第一种边循环节长度为 $\frac l 2$ ，这些边有 $\frac l 2$ 条，另一些边循环节长度为 $l$ ，这些边有 $\frac{l(l-2)}{2}$ 条，因此总循环节个数为： $\frac{\frac l 2}{\frac l 2}+\frac{\frac{l(l-2)}{2}}{l}=1+\frac{l-2}{2}=\frac l 2$ 。

所以对于一个置换，总循环节个数为： $$ \sum_{i=1}^k\lfloor\frac{l_{i}}{2}\rfloor+\sum_{i=1}^{k-1}\sum_{j=i+1}^k\gcd(l_i,l_j) $$ 但是我们显然不能枚举所有的置换然后求解，发现实际有用的只有 $l_i$ ，那我们就可以枚举一下整数划分，然后统计有多少置换的循环是这个划分，然后按照上面的式子计算就可以了。

于是问题变成了对于一个划分，有多少种置换的循环表示和他相同，由于一个长为 $l$ 的循环的个数为 $(l-1)!$ （因为循环移位本质相同），那么我们就可以先枚举一个多重集排列数，然后会发现有的相同，它们之间的顺序是不应该被考虑的，于是答案就是： $$ S=\frac{n!}{\prod l_i!\prod cnt[i]!}\times\prod (l_i-1)!=\frac{n!}{\prod l_i\prod cnt[i]!} $$ 于是我们可以暴力枚举集合划分数，然后用上面那个公式统计一下，最后除掉置换总个数 $n!$ 即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

typedef long long ll;

ll n,c,p;

ll ans = 0;

#define MAXN 55

ll fac[MAXN];

ll power(ll a,ll b)

{

	ll res = 1;

	while(b > 0)

	{

		if(b & 1)res = res * a % p;

		a = a * a % p;

		b = b >> 1;

	}

	return res;

}

ll cnt[MAXN];

ll gcd(ll a,ll b){return (b == 0 ? a : gcd(b,a % b));}

ll l[MAXN];

ll calc(ll x)

{

	ll m = 0;

	for(int i = 1;i <= x;++i)m += l[i] / 2;

	for(int i = 1;i < x;++i)for(int j = i + 1;j <= x;++j)m += gcd(l[i],l[j]);

	ll s = 1;

	for(int i = 1;i <= x;++i)s = s * l[i] % p;

	for(int i = 1;i <= n;++i)s = s * fac[cnt[i]] % p;

	return power(s,p - 2) * power(c,m) % p;

}

void dfs(ll cur,ll rem,ll low)

{

	if(rem == 0)

	{

		ans = (ans + calc(cur - 1)) % p;

		return;

	}

	for(ll i = low;i <= rem;++i)

	{

		++cnt[i];l[cur] = i;

		dfs(cur + 1,rem - i,i);

		--cnt[i];

	}

	return;

}

int main()

{

	scanf("%lld%lld%lld",&n,&c,&p);

	fac[0] = 1;

	for(int i = 1;i <= n;++i)fac[i] = fac[i - 1] * i % p;

	dfs(1,n,1);

	cout << ans << endl;

	return 0;

}