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;

typedef long long ll;
typedef pair<int, int> PII;

#define fi first
#define se second
#define mp make_pair
#define pb push_back

#define P 1000000007
#define N 310
int n;
int f[N][N][N*2];
int d[N];
int F[N];
int IF[N];

void gcd(int a,int b,int &x,int &y) {
  if(b==0){x=1,y=0;return;}
  gcd(b,a%b,y,x),y-=a/b*x;
}
int inv(int n) {
  int x,y;gcd(n,P,x,y);
  if(x<0)x+=P;return x;
}

const int INV2 = inv(2);

int main() {
	F[0]=1;for(int i=1;i<N;i++)F[i]=(ll)F[i-1]*i%P;
	IF[N-1]=inv(F[N-1]);for(int i=N-1;i;i--)IF[i-1]=(ll)IF[i]*i%P;
	cin >> n;
	for (int i = 0; i < n; i ++) cin >> d[i];
	f[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 ++) if (f[i][j][k]) {
				f[i+1][j][k] = (f[i+1][j][k] + (ll)f[i][j][k]*IF[d[i]-1])%P;
				if (d[i] >= 2) f[i+1][j+1][k+d[i]-2] = (f[i+1][j+1][k+d[i]-2] + (ll)f[i][j][k]*IF[d[i]-2])%P;
			}
	int S = 0;
	for (int i = 3; i <= n; i ++)
		for (int j = 0; j <= 2*n; j ++) if (f[n][i][j]) {
			if (i < n && j == 0) continue;
			if (i == n && j == 0) {
				S = (S + (ll)f[n][i][j]*F[i-1]%P*INV2%P)%P;
				continue;
			}
			//printf ("%d %d %lld\n", i, j, (ll)f[n][i][j]);
			//printf ("%d %d %lld\n", i, j, (ll)f[n][i][j]*F[i-1]%P*INV2%P*F[j]%P*IF[j-1]%P*F[n-1-i]%P);
			S = (S + (ll)f[n][i][j]*F[i-1]%P*INV2%P*F[j]%P*IF[j-1]%P*F[n-1-i]%P)%P;
		}
	cout << S << endl;
	return 0;
}