分析
显然对于合法的图，满足不在最短路树上边连接的点在同一层。
设 $f_{i,j}$ 表示前 $i$ 个点，$[i-j+1,i]$ 中的点在同一层时的方案数，$g_{i,j,k}$ 表示这一层有 $i$ 个点，上一层有 $j$ 个度数为 $2$ 的点、$k$ 个度数为 $3$ 的点时从上一层往这一层连边和上一层内部连边的方案数。
$f$ 的转移不难得到：枚举上一层的点数，有
$$
f_{i,j}=\sum_{k=1}^{i-j+1}f_{i-j,k}g_{j,c_2,c_3}
$$
这里的 $c_2$ 和 $c_3$ 表示上一层中度数为 $2$ 和 $3$ 的点的数量。
考虑 $g$ 的转移。首先有边界 $g_{0,0,0}=1$。
先考虑 $g_{0,0,k}$ 的转移。此时上一层内所有点会往同一层的点连两条边，因此一定连成若干个环。枚举一个点所在的环长即可得到转移从而有
$$
g_{0,0,k}=\sum_{l=3}^kg_{0,0,k-l}{k-1\choose l-1}N_l
$$
这里的 $N_l$ 是项链数。
再考虑 $g_{0,j,k}$ 的转移。假设加入一个度数为 $2$ 的点，则它需要向同层的点连一条边，讨论一下连向的点的度数可以得到
$$
g_{0,j,k}=(j-1)\times g_{0,j-2,k}+k\times g_{0,j,k-1}
$$
最后考虑 $g_{i,j,k}$ 的转移。对于每个点讨论一下它的父节点的度数可以得到
$$
g_{i,j,k}=j\times g_{i-1,j-1,k}+k\times g_{i-1,j+1,k-1}
$$
答案为
$$
\sum_{i=1}^{n-1}f_{n,i}\times g_{0,c_2,c_3}
$$
这里的 $c_2$ 和 $c_3$ 表示最后 $n$ 个点中度数为 $2$ 和 $3$ 的点的数量。
代码
// ====================================
// author: M_sea
// website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;
int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=50+10;
const int mod=1e9+7;
int n,d[N],C[N][N],Ne[N];
int g[N][N][N],f[N][N];
int main() {
n=read();
for (int i=1;i<=n;++i) d[i]=read();
for (int i=C[0][0]=1;i<=n;++i)
for (int j=C[i][0]=1;j<=i;++j)
C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
Ne[2]=Ne[3]=1;
for (int i=4;i<=n;++i) Ne[i]=1ll*Ne[i-1]*(i-1)%mod;
g[0][0][0]=1;
for (int k=1;k<=n;++k)
for (int l=3;l<=k;++l)
g[0][0][k]=(g[0][0][k]+1ll*g[0][0][k-l]*C[k-1][l-1]%mod*Ne[l])%mod;
for (int j=1;j<=n;++j)
for (int k=0;j+k<=n;++k) {
if (j>=2) g[0][j][k]=(g[0][j][k]+1ll*g[0][j-2][k]*(j-1))%mod;
if (k>=1) g[0][j][k]=(g[0][j][k]+1ll*g[0][j][k-1]*k)%mod;
}
for (int i=1;i<=n;++i)
for (int j=0;i+j<=n;++j)
for (int k=0;i+j+k<=n;++k) {
if (j) g[i][j][k]=(g[i][j][k]+1ll*g[i-1][j-1][k]*j)%mod;
if (k) g[i][j][k]=(g[i][j][k]+1ll*g[i-1][j+1][k-1]*k)%mod;
}
f[d[1]+1][d[1]]=1;
for (int i=d[1]+2;i<=n;++i)
for (int j=1;j+d[1]+1<=i;++j)
for (int k=1,c2=0,c3=0;i-j-k+1>=0;++k) {
d[i-j-k+1]==2?++c2:++c3;
f[i][j]=(f[i][j]+1ll*f[i-j][k]*g[j][c2][c3])%mod;
}
int ans=0;
for (int i=1,c2=0,c3=0;i<n;++i) {
d[n-i+1]==2?++c2:++c3;
ans=(ans+1ll*f[n][i]*g[0][c2][c3])%mod;
}
printf("%d\n",ans);
return 0;
}