首先发现一次生长相当于去掉一个分支并增加两个分支， 那么所有树出现的概率都是相同的， 一共有 N! 种树。
所以要求输出的那个东西就是不便度的平均数 * 树的总数， 即所有树的不便度之和。
对于某棵树的不便度， 把它拆到边上， 具体地， 这棵树的不便度等于 \(\sum_u siz(u) * (n - siz(u))\)。
设 cntu,s 表示点 u 的 siz 为 s 的方案数。（1≤s≤n-u+1）
首先， 生成 1~u， \(\color{red}{u!}\)。
其次， 决定 u 子树中的点的标号，\(\color{red}{\dbinom {n-u}{s-1}}\)， 然后生成以 u 为根的子树， \(\color{red}{s!}\)。
然后生成整棵树的其余部分，\(\color{red}{(u-1)(u-1+1)\cdots(u-1+(n-u-s+1)-1)} = \dfrac{(n-s-1)!}{(u-2)!}\)
所以答案就是：
\[\sum_{u=1}^n\sum_{s=1}^{n-u+1} s(n-s)u!\binom{n-u}{s-1}s!\frac{(n-s-1)!}{(u-2)!}
\]
这道题的模数不保证是质数， 组合数可以预处理，只需要化掉除法：
\[\begin{align}
&s(n-s)u!\binom{n-u}{s-1}s!\frac{(n-s-1)!}{(u-2)!}\&= s\binom{n-u}{s-1}s!(n-s)!(u-1)u
\end{align}
\]
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int N = 2e3 + 3;
int n, mo;
LL C[N][N], fac[N];
int main() {
scanf("%d%d", &n, &mo);
fac[0] = 1ll, C[0][0] = 1ll;
for(int i = 1; i <= n; ++i) fac[i] = fac[i-1] * (LL)i % mo;
for(int i = 1; i <= n; ++i) {
C[i][0] = 1ll;
for(int j = 1; j <= n; ++j) C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mo;
}
LL ans = 0ll;
for(int u = 1; u <= n; ++u) {
for(int s = 1; s <= n-u+1; ++s) {
ans += (LL)s * C[n-u][s-1] % mo * fac[s] % mo * fac[n-s] % mo * (LL)u % mo * (LL)(u-1) % mo;
ans %= mo;
}
}
cout << (ans%mo + mo) % mo;
return 0;
}