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 <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 300;
const int MOD = int(1E9) + 7;
const int INV2 = (MOD + 1) / 2;

inline int add(int x, int y) {return (x + y >= MOD ? x + y - MOD : x + y);}
inline int sub(int x, int y) {return (x - y < 0 ? x - y + MOD : x - y);}
inline int mul(int x, int y) {return 1LL * x * y % MOD;}

int pow_mod(int b, int p) {
	int ret = 1;
	for(int i=p;i;i>>=1,b=mul(b,b))
		if( i & 1 ) ret = mul(ret, b);
	return ret;
}

int fct[2*MAXN + 5], ifct[2*MAXN + 5];
void init() {
	fct[0] = 1; for(int i=1;i<=2*MAXN;i++) fct[i] = mul(fct[i - 1], i);
	for(int i=0;i<=2*MAXN;i++) ifct[i] = pow_mod(fct[i], MOD - 2);
}

int dp[2][MAXN + 5][MAXN + 5];

int d[MAXN + 5], N;
int main() {
	init(), scanf("%d", &N);
	for(int i=1;i<=N;i++)
		scanf("%d", &d[i]), d[i]--;
	int tot = 0; dp[0][0][0] = 1;
	for(int i=1;i<=N;i++) {
		if( d[i] ) {
			for(int j=0;j<i;j++)
				for(int k=0;k<=tot;k++)
					dp[1][j][k] = dp[0][j][k];
			for(int j=0;j<i;j++)
				for(int k=0;k<=tot;k++)
					dp[0][j+1][k+d[i]-1] = add(dp[0][j+1][k+d[i]-1], mul(d[i], dp[1][j][k]));
			tot += d[i] - 1;
		}
	}
	int ans = mul(mul(fct[N-1], INV2), dp[0][N][0]), tmp = 1;
	for(int i=1;i<=N;i++) tmp = mul(tmp, ifct[d[i]]);
	for(int i=3;i<N;i++)
		for(int j=1;j<=tot;j++) {
			int coef = mul(mul(fct[i-1], INV2), mul(fct[N-i-1], tmp));
			ans = add(ans, mul(mul(coef, j), dp[0][i][j]));
		}
	printf("%d\n", ans);
}