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<bits/stdc++.h>
using namespace std;

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

const int mod=1000000007;
int mpow(int n,int m){
    int ret=1;
    while(m){
        if(m&1)ret=ret*n%mod;
        n=n*n%mod;
        m>>=1;
    }
    return ret;
}


inline void add(int &a,int b){
    a+=b;
    if(a>=mod)a-=mod;
}
const int FACT_SIZE=1111111;
int fact[FACT_SIZE];
int inv[FACT_SIZE];
struct fact_exec{
    fact_exec(){
        fact[0]=1;
        for(int i=1;i<FACT_SIZE;i++)fact[i]=fact[i-1]*i%mod;
        inv[FACT_SIZE-1]=mpow(fact[FACT_SIZE-1],mod-2);
        for(int i=FACT_SIZE-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
    }
}factexec;
int nCk(int n,int k){
    return fact[n]*inv[k]%mod*inv[n-k]%mod;
}
int nPk(int n,int k){
    return fact[n]*inv[n-k]%mod;
}

int N;
int D[333];

int dp[2][666][333];

signed main(){
    cin>>N;
    rep(i,N)cin>>D[i];

    if(count(D,D+N,2)==N){
        cout<<fact[N-1]*inv[2]%mod<<endl;
        return 0;
    }

    dp[0][0][0]=1;
    rep(i,N){
        rep(j,2*N){
            rep(k,N){
                add(dp[(i+1)&1][j][k],dp[i&1][j][k]*inv[D[i]-1]%mod);
                if(D[i]>=2)add(dp[(i+1)&1][j+D[i]-2][k+1],dp[i&1][j][k]*inv[D[i]-2]%mod);
                dp[i&1][j][k]=0;
            }
        }
    }

    int ans=0;
    for(int i=1;i<2*N;i++){
        for(int j=3;j<N;j++){
            int tmp=dp[N&1][i][j];
            tmp=tmp*i%mod;
            tmp=tmp*fact[j-1]%mod;
            tmp=tmp*inv[2]%mod;
            tmp=tmp*fact[N-j-1]%mod;
            add(ans,tmp);
        }
    }
    cout<<ans<<endl;
    return 0;
}
