除了神仙啥都不想说了orz->

首先生成二叉树的时候，第一个点有\(1\)种选法，第二个点有\(2\)种选法...第\(n\)个点有\(n\)种选法，于是树的形态共有\(n!\)种，需要求它们总共的点对距离和

发现按点来考虑太麻烦了，我们按边来考虑贡献，对\(i\)的父亲边来说，有\(sz_i(n-sz_i)\)个点对会经过这一条边，所以这一条边对答案就有这么多的贡献

于是考虑一下\(O(n^2)\)的枚举，设\(sz_i\)为子树的大小，\(i\)为当前点，那么这棵子树的形态有\(sz_i!\)种，子树的编号有\(C_{n-i}^{sz_i-1}\)种（生成\(i\)之后从剩下的点中选出\(sz_i-1\)个让他们在\(i\)的子树里），于是总的方案数就是\(sz_i!C_{n-i}^{sz_i-1}\)种

然后考虑子树外的方案数，生成\(i\)之前共有\(i!\)种方法，而生成\(i\)之后的点不能放到\(i\)的子树中，于是后面的点有\((i+1-2),(i+2-2),...(n-sz_i+1-2)\)种方法（因为放到\(i\)的子树中的点并不会影响外面的点的方案数），乘起来化简一下就是\(i(i-1)(n-sz_i-1)!\)种方法

于是最后的答案就是\[ans=\sum_{i=2}^{n}\sum_{j=1}^{n-i+1}j(n-j)j!C_{n-i}^{j-1}i(i-1)(n-j-1)!\]

//minamoto#include
    
     #define ll long longusing namespace std;const int N=2005;int n;ll mod,dp[N][N],C[N][N],fac[N],res;int main(){//  freopen("testdata.in","r",stdin);    scanf("%d%lld",&n,&mod),fac[0]=1;    for(int i=0;i<=n;++i)C[i][i]=C[0][i]=1;    for(int i=0;i<=n;++i)for(int j=1;j