考虑生成一颗二叉树的过程，加入第一个节点方案数为(1)，加入第二个节点方案数为(2)，加入第三个节点方案数为(3)，发现生成一颗(n)个节点的二叉树的方案数为(n!)。
所以题目中所求即为点与点之间的距离之和，考虑每一条边的贡献，即(sumlimits_esize_x imes size_y)，(x)和(y)为这条边的两个端点。
可以枚举每一个节点(i)，再枚举节点(i)子树大小(j)，其和父亲的连边对答案的贡献为(j(n-j))，然后贡献再乘上这个状态对应的方案数，就是所求的答案，因此问题转化为了求节点(i)子树大小为(j)的方案数。
可以把计算方案数看作三部分，安排点(i)子树中点的方案数，安排比(i)编号小的点的方案数，安排比(i+j-1)编号大的点的方案数。
考虑点(i)子树为一颗大小为(j)的二叉树，生成这个子树的方案数为(j!)。其中的点是有编号的，并且编号都比(i)大，所以安排子树中的点方案数还要考虑选出哪些点，总方案数即为(j!inom{n-i}{j-1})。
比点(i)编号小的点的安排方案数即为生成一颗(i)个点的二叉树的方案数，即(i!)。
比点(i)编号大的点在安排时都不能放到(i)的子树中。考虑安排好(i)子树内所有点后，即安排好前(i+j-1)个点后，再新加入一个点的方案数为(i-1)，加入第二点的方案数为(i)，加入第二点的方案数为(i+1)，一直加到最后一个点，加入最后一个点的方案数为(n-j-1)，总方案数即为(frac{(n-j-1)!}{(i-2)!})。
把边的贡献和上面得出的方案数乘起来，即为答案，得：
[sum_{i=1}^n sum_{j=1}^{n-i+1} j(n-j)j!inom{n-i}{j-1}i!frac{(n-j-1)!}{(i-2)!}
]
考虑模数可能没有逆元，所以将式子进一步化简，去掉除法，得：
[sum_{i=1}^n sum_{j=1}^{n-i+1} j(n-j)j!inom{n-i}{j-1}(n-j-1)!i(i-1)
]
然后预处理阶乘和组合数，(n^2)计算即可。
(code:)
#include<bits/stdc++.h>
#define maxn 2010
using namespace std;
typedef long long ll;
template<typename T> inline void read(T &x)
{
x=0;char c=getchar();bool flag=false;
while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
if(flag)x=-x;
}
ll n,p,ans;
ll f[maxn],C[maxn][maxn];
void init()
{
f[0]=1;
for(int i=1;i<=n;++i) f[i]=f[i-1]*i%p;
for(int i=0;i<=n;++i) C[i][0]=1;
for(int i=1;i<=n;++i)
for(int j=1;j<=i;++j)
C[i][j]=(C[i-1][j-1]+C[i-1][j])%p;
}
int main()
{
read(n),read(p),init();
for(int i=1;i<=n;++i)
for(int j=1;j<=n-i+1;++j)
ans=(ans+j*(n-j)%p*f[j]%p*C[n-i][j-1]%p*f[n-j-1]%p*i%p*(i-1)%p)%p;
printf("%lld",ans);
return 0;
}