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 PB push_back
#define MP make_pair
#define LL long long
#define int LL
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define RE(i,n) FOR(i,1,n)
#define REP(i,n) FOR(i,0,(int)(n)-1)
#define R(i,n) REP(i,n)
#define VI vector<int>
#define PII pair<int,int>
#define LD long double
#define FI first
#define SE second
#define st FI
#define nd SE
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())

template<class C> void mini(C &a4, C b4) { a4 = min(a4, b4); }
template<class C> void maxi(C &a4, C b4) { a4 = max(a4, b4); }

template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;cerr<<'='<<h<<','; _dbg(sdbg+1, a...);
}

template<class T> ostream &operator<<(ostream& os, vector<T> V) {
  os << "["; for (auto vv : V) os << vv << ","; return os << "]";
}
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.st << "," << P.nd << ")";
}

#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

const int MAX = 303;
const int P = 1e9 + 7;
int n,d[MAX];
int sil[MAX],odw[MAX];
int dp[MAX][MAX][MAX];
void add(int &a,int b){
  a += b;
  if(a >= P)
    a -= P;
}
int mnu(int a,int b){
  return a * b % P;
}
int pot(int a,int w){
  int r = 1;
  while(w){
    if(w & 1){
      r = mnu(r,a);
    }
    w/=2;
    a = mnu(a,a);
  }
  return r;
}

int dwu(int a,int b){
  return mnu(mnu(sil[a],odw[b]),odw[a-b]);
}

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(11);
  cerr << fixed << setprecision(6);
  sil[0] = 1;
  R(i,MAX-1){
    sil[i+1] = mnu(sil[i], i + 1);
  }
  R(i,MAX){
    odw[i] = pot(sil[i], P - 2);
  }
  cin >> n;
  int same2 = 1;
  R(i,n){
    cin >> d[i];
    if(d[i] != 2){
      same2 = 0;
    }
  }
  if(same2){
    cout << mnu(sil[n-1],odw[2]) << "\n"; 
    return 0;
  }
  debug("??");
  dp[0][0][0] = 1;
  R(i,n)R(w,n+1)R(s,n+1){
    debug(i,w,s);
    if(d[i] >= 2){
      int pom = (w <= 2 ? 1 : w);
      add(dp[i+1][w+1][s + d[i] - 2],
          mnu(mnu(dp[i][w][s], pom), dwu(s + d[i] - 2, d[i] - 2))
      );
    }
    add(dp[i+1][w][s], mnu(dp[i][w][s],odw[d[i]-1]));
  }
  int res = 0;
  for(int w = 3; w < n; w++)for(int s = 1; s <= n; s++){
    debug(n-w-1);
    add(res, mnu(mnu(dp[n][w][s], sil[n - w - 1]), odw[s-1]));
  }
  cout << res << "\n";
}
