好像又是神仙dp。。。。gan了一早上
首先这是个计数类问题，上DP，
对于一个最小生成树，按照kruskal是一个个联通块，枚举边小到大合成的
假如当前边是树边，那么转移应该还是枚举两个块然后合并
假如不是树边那么就在所有联通块所有非树边中任选一条
两个相邻树边之间的非树边方案应该是P（所有联通块总边数-（当前枚举到那条边-1），r-l-1）
然而按照我现在的智商还是不会捉
%了题解发现一个非常强大的性质，就是对于一个整数的无序拆分很小，40只有37338
设f[zt]，其中zt表示一个状态，由一些联通块的大小组成，总和为n
这样可以爆搜一波把所有无序拆分也就是状态弄出来，并给一个新编号
转移就是枚举两个联通块然后合并
若第i,j个合并
(新状态的方案)+=(这个状态的方案)*(两条树边之间其他边选择的方案)*(第i个联通块的大小)*(第j个联通块的大小)
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
typedef long long LL;
const LL mod=1e9+; int n;
struct zhuangtai
{
int u[];
friend bool operator >(zhuangtai z1,zhuangtai z2)
{
if(z1.u[]==z2.u[])
{
for(int i=;i<=z1.u[];i++)
if(z1.u[i]!=z2.u[i])return z1.u[i]>z2.u[i];
}
return z1.u[]>z2.u[];
}
friend bool operator <(zhuangtai z1,zhuangtai z2)
{
if(z1.u[]==z2.u[])
{
for(int i=;i<=z1.u[];i++)
if(z1.u[i]!=z2.u[i])return z1.u[i]<z2.u[i];
}
return z1.u[]<z2.u[];
}
int getsum()
{
int ret=;
for(int i=;i<=u[];i++)
ret=(ret+(u[i]*(u[i]-)/)%mod)%mod;
return ret;
}
}mp[];int z,g[];
bool cmp(zhuangtai z1,zhuangtai z2){return z1>z2;}
map<zhuangtai,int>id;//通过状态找编号
void dfs(int d,int last)//预处理拆分n的方案
{
if(d==n)
{
z++;
for(int i=;i<=g[];i++)mp[z].u[i]=g[i];
return ;
}
for(int i=last;i+d<=n;i++)
{
g[++g[]]=i;
dfs(i+d,i);
g[g[]--]=;
}
} LL quick_pow(LL A,LL p)
{
LL ret=;
while(p!=)
{
if(p%==)ret=ret*A%mod;
A=A*A%mod;p/=;
}
return ret;
}
LL fac[],fac_inv[];
LL getP(int n,int m){return fac[n]*fac_inv[n-m]%mod;} zhuangtai t;int h[];
int getnzt(int zt,int x,int y)
{
memcpy(h,mp[zt].u,sizeof(h));
int d=h[x]+h[y]; memset(t.u,,sizeof(t.u));
for(int i=;i<=h[];i++)
{
if(i!=x&&i!=y)
{
if(d!=-&&h[i]>d)t.u[++t.u[]]=d,d=-;
t.u[++t.u[]]=h[i];
}
}
if(d!=-)t.u[++t.u[]]=d;
return id[t];
}
int a[];LL f[];
int main()
{
fac[]=,fac_inv[]=;
for(int i=;i<=;i++)
fac[i]=fac[i-]*i%mod,fac_inv[i]=quick_pow(fac[i],mod-); scanf("%d",&n);
for(int i=;i<n;i++)scanf("%d",&a[i]);
z=;dfs(,);
sort(mp+,mp+z+,cmp);
for(int i=;i<=z;i++)id[mp[i]]=i; memset(f,,sizeof(f));f[]=;
for(int zt=;zt<=z;zt++)
if(f[zt]>)
{
int e=n-mp[zt].u[]+;//轮到第几条边用来合并
LL P=getP(mp[zt].getsum()-(a[e-]),a[e]-a[e-]-);//两条树边中间其他边选择的方案数 for(int i=;i<=mp[zt].u[];i++)
for(int j=i+;j<=mp[zt].u[];j++)
{
int nzt=getnzt(zt,i,j);
f[nzt]=(f[nzt]+f[zt]*P%mod*mp[zt].u[i]%mod*mp[zt].u[j]%mod)%mod;
}
}
int rst=n*(n-)/-a[n-];
printf("%lld\n",f[z]*getP(rst,rst)%mod);
return ;
}