Snuke has come up with the following problem.

> You are given a sequence d of length N. Find the number of the undirected graphs with N vertices labeled 1,2,...,N satisfying the following conditions, modulo 10^{9} + 7:
>
>   * The graph is simple and connected.
>   * The degree of Vertex i is d_i.
>


When 2 \leq N, 1 \leq d_i \leq N-1, {\rm Σ} d_i = 2(N-1), it can be proved that the answer to the problem is \frac{(N-2)!}{(d_{1} -1)!(d_{2} - 1)! ... (d_{N}-1)!}.

Snuke is wondering what the answer is when 3 \leq N, 1 \leq d_i \leq N-1, { \rm Σ} d_i = 2N. Solve the problem under this condition for him.

Constraints

* 3 \leq N \leq 300
* 1 \leq d_i \leq N-1
* { \rm Σ} d_i = 2N

Input

Input is given from Standard Input in the following format:


N
d_1 d_2 ... d_{N}


Output

Print the answer.

Examples

Input

5
1 2 2 3 2


Output

6


Input

16
2 1 3 1 2 1 4 1 1 2 1 1 3 2 4 3


Output

555275958
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;

#define LL long long
#define DB double
#define MAXN 300
#define Pr pair<LL,int>
#define X first
#define Y second
#define INF 1000000000
#define MOD 1000000007
#define mem(x,v) memset(x,v,sizeof(x))

LL read(){
    LL x=0,F=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')F=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*F;
}
int add(int a,int b){return (a+b>=MOD)?a+b-MOD:a+b;}
int dec(int a,int b){return (a-b<0)?a-b+MOD:a-b;}
int mul(int a,int b){return (1LL*a*b)%MOD;}
int fst_pow(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=mul(res,a);
        a=mul(a,a),b>>=1;
    }return res;
}

int n,d[MAXN+5],dp[MAXN+5][MAXN+5],tot,inv2;
int fac[MAXN+5],ifac[MAXN+5],ans,xd;
void upd(int &x,int y){x=add(x,y);}

void prepare(){
    fac[0]=1;
    for(int i=1;i<=MAXN;i++)fac[i]=mul(fac[i-1],i);
    ifac[MAXN]=fst_pow(fac[MAXN],MOD-2);
    for(int i=MAXN;i>=1;i--)ifac[i-1]=mul(ifac[i],i);
}

int main(){
    prepare();
    n=read(),inv2=(MOD+1)>>1;
    for(int i=1;i<=n;i++)d[i]=read()-1;
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    if(d[i]){
        for(int j=i-1;j>=0;j--)
            for(int k=0;k<=tot;k++)
            upd(dp[j+1][k+d[i]-1],mul(d[i],dp[j][k]));
        tot+=d[i]-1;
    }
    ans=mul(mul(fac[n-1],inv2),dp[n][0]),xd=1;
    for(int i=1;i<=n;i++)xd=mul(xd,ifac[d[i]]);
    for(int i=3;i<n;i++)//**从3开始
        for(int j=1;j<=tot;j++){
            int c=mul(mul(fac[i-1],inv2),mul(fac[n-i-1],xd));
            ans=add(ans,mul(mul(c,j),dp[i][j]));
        }
    printf("%d",ans);
}
