记录编号	578250	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[雅礼集训 2018 Day1] 树	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2023-02-24 23:23:47	内存使用	0.00 MiB

// Problem: #6495. 「雅礼集训 2018 Day1」树
// Contest: LibreOJ
// URL: https://loj.ac/p/6495
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using i128 = __int128;
using i64 = long long;
using u64 = unsigned long long;
using ld = long double;

const int N = 30;
i128 C[N][N],f[N][N],p;
int n;

i128 power(i128 x,i128 y) {
	i128 ans = 1;
	for(;y;y >>= 1) {
		if(y & 1)
			ans = 1ll * ans * x % p;
		x = 1ll * x * x % p;
	}
	return ans;
}

void print(i128 x) {
	if(x > 9)
		print(x / 10);
	putchar(x % 10 + '0');
	return ;
}

i128 read() {
	i128 s = 0;
	char c = getchar();
	for(;c < '0'||c > '9';c = getchar());
	for(;c >= '0'&&c <= '9';c = getchar())
		s = (s << 1) + (s << 3) + (c ^ '0');
	return s;
}

int main() {
	freopen("shu.in","r",stdin);
	freopen("shu.out","w",stdout);
	scanf("%d",&n);
	p = read();
	f[1][1] = 1;
	for(int i = 0;i <= n;++ i) {
		C[i][0] = 1;
		for(int j = 1;j <= i;++ j)
			C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
	}
	f[1][1] = 1;
	for(int i = 2;i <= n;++ i) {
		for(int j = 1;j <= n;++ j) {
			f[i][j] = f[i - 1][j - 1];
			for(int k = 1;k <= i - 2;++ k) {
				for(int t = 1;t <= k&&t < j - 1;++ t)
					f[i][j] += f[k][t] * C[i - 2][k - 1] * f[i - k][j];
				i128 ans = 0;
				for(int t = 1;t <= j;++ t)
					ans += f[i - k][t];
				f[i][j] += f[k][j - 1] * C[i - 2][k - 1] * ans;
			}
		}
	}
	i128 sum = 0,fac = 1;
	for(int i = 1;i <= n;++ i)
		sum += i * f[n][i];
	for(int i = 1;i < n;++ i)
		fac *= i;
	print((sum * 2 + fac) / fac / 2);
	puts("");
	sum = sum % p * power(fac % p , p - 2) % p;
	print(sum);
	return 0;
}