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 <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define N_MAX 1000

using namespace std;
typedef long long ll;

const ll MOD = 1000000007;

ll inv[N_MAX],fac[N_MAX],finv[N_MAX];

void init(){
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    for(int i=2;i<N_MAX;i++){
        inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
        fac[i]=fac[i-1]*(ll) i%MOD;
        finv[i]=finv[i-1]*inv[i]%MOD;
    }
}

ll dp[3][305][605];

int N, d[305];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(10) << fixed;
    init();
    cin >> N;
    for(int i = 0; i < N; i++) cin >> d[i];
    dp[0][0][0] = 1;
    for(int i = 0; i < N; i++){
        for(int j = 0; j <= i; j++){
            for(int k = 0; k <= 2*N; k++){
                dp[(i+1)%2][j][k] = 0;
            }
        }
        for(int j = 0; j <= i; j++){
            for(int k = 0; k+d[i] <= 2*N; k++){
                // cycleに使う
                if(d[i] >= 2){
                    dp[(i+1)%2][j+1][k+d[i]] += (dp[i%2][j][k]*finv[d[i]-2])%MOD;
                    dp[(i+1)%2][j+1][k+d[i]] %= MOD;
                }
                // cycleに使わない
                dp[(i+1)%2][j][k] += (dp[i%2][j][k]*finv[d[i]-1])%MOD;
                dp[(i+1)%2][j][k] %= MOD;
            }
        }
    }
    ll ans = dp[N%2][N][2*N];
    ans *= fac[N-1];
    ans %= MOD;
    ans *= inv[2];
    ans %= MOD;
    for(int j = 3; j <= N-1; j++){
        for(int k = 2*j+1; k <= 2*N; k++){
            ll tmp = dp[N%2][j][k];
            tmp *= fac[j-1];
            tmp %= MOD;
            tmp *= inv[2];
            tmp %= MOD;
            tmp *= fac[N-j-1];
            tmp %= MOD;
            tmp *= finv[k-2*j-1];
            tmp %= MOD;
            // そととのつなぎ方
            tmp *= fac[k-2*j];
            tmp %= MOD;
            ans += tmp;
            ans %= MOD;
            // cout << fac[j-1] << ' ' << fac[N-2*j-2] << ' ' << finv[k-2*j-1] << endl;
            // cout << "dp[" << N << "][" << j << "][" << k << "] = " << dp[N][j][k] << ' ' << tmp << endl;
        }
    }
    cout << ans << endl;
}