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 FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
#define __builtin_popcount __builtin_popcountll
using ll=long long; using ld=long double;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2;
template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);}
template <typename T> inline void writeln(T x){write(x); putchar('\n');}
template <typename CT, typename T> inline void reset_container(CT &c, int sz, T v){c.resize(sz); for(auto &x: c) x=v;}
#define taskname "B"
int n;
int d[301];
const ll base=1000000007;
ll power(ll a, ll b){
    if(b==0) return 1;
    ll t=power(a, b/2);
    t=(t*t)%base;
    if(b%2) t=(t*a)%base;
    return t;
}
ll f[601];
ll r[601];
ll dp[301][601];
ll temp[301][601];
int main(){
    #ifdef Aria
        if(fopen(taskname".in", "r"))
            freopen(taskname".in", "r", stdin);
    #endif // Aria
    f[0]=1;
    FOR(i, 1, 600) f[i]=(f[i-1]*i)%base;
    r[600]=power(f[600], base-2);
    DFOR(i, 600, 1) r[i-1]=(r[i]*i)%base;
//    bug((((((f[12]*r[2])%base*r[2])%base*r[3])%base*r[3])%base*18)%base);
    read(n);
    FOR(i, 1, n) read(d[i]);
    dp[0][0]=r[2];
    FOR(i, 1, n){
        FOR(j, 0, n) FOR(k, j+j, n+n) temp[j][k]=0;
        FOR(j, 0, n) FOR(k, j+j, n+n) if(dp[j][k]){
            if(d[i]>=2) temp[j+1][k+d[i]]=(temp[j+1][k+d[i]]+dp[j][k]*r[d[i]-2])%base;
            temp[j][k]=(temp[j][k]+dp[j][k]*r[d[i]-1])%base;
        }
        FOR(j, 0, n) FOR(k, j+j, n+n) dp[j][k]=temp[j][k];
    }
//    bug()
    ll ans=(dp[n][n+n]*f[n-1])%base;
    FFOR(i, 3, n) FOR(k, i+i+1, n+n) if(dp[i][k]){
        ans=(ans+(((f[n-i-1]*(k-2*i))%base*f[i-1])%base)*dp[i][k])%base;
    }
//    ans=(ans*r[2])%base;
    writeln(ans);
}