一个有n个结点的树，设它的结点分别为v1, v2, …, vn，已知第i个结点vi的度数为di，问满足这样的条件的不同的树有多少棵。给定n，d1, d2, …, dn，编程需要输出满足d(vi)=di的树的个数。

第一行是一个正整数n，表示树有n个结点。第二行有n个数，第i个数表示di，即树的第i个结点的度数。其中1<=n<=150，输入数据保证满足条件的树不超过10^17个。

输出满足条件的树有多少棵。

 #include<iostream>

 #include<cstdio>

 #define N (159)

 #define LL long long

 #define MOD (100000000000000007LL)

 LL n,sum,d[N],fac[N];

 LL Mul(LL a,LL b)

 {

     LL tmp=a*b-(LL)((long double)a*b/MOD+0.1)*MOD;

     return tmp<?tmp+MOD:tmp;

 }

 int main()

 {

     scanf("%lld",&n);

     fac[]=;

     for (int i=; i<=n; ++i)

     {

         scanf("%lld",&d[i]), sum+=d[i];

         if (!d[i] && n>) {puts(""); return ;}

         fac[i]=Mul(fac[i-],i);

     }

     if (sum!=n*- || n== && d[]) {puts(""); return ;}

     if (n==) {puts(""); return ;}

     LL ans=fac[n-];

     for (int i=; i<=n; ++i)

         ans=Mul(ans,fac[d[i]-]);

     printf("%lld\n",ans);

 }