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>
#define endl '\n'
using namespace std;
typedef long long ll;
int read()
{
	int out = 0, sgn = 1;
	char jp = getchar();
	while (jp != '-' && (jp < '0' || jp > '9'))
		jp = getchar();
	if (jp == '-')
		sgn = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * sgn;
}
const int P = 1e9 + 7;
int add(int a, int b)
{
	return a + b >= P ? a + b - P : a + b;
}
void inc(int &a, int b)
{
	a = add(a, b);
}
int mul(int a, int b)
{
	return 1LL * a * b % P;
}
int fpow(int a, int b)
{
	int res = 1;
	while (b)
	{
		if (b & 1)
			res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}
const int N = 300 + 10;
int n, deg, fac[N], invfac[N], dp[N][N][2], ans;
int main()
{
	n = read();
	fac[0] = 1;
	for (int i = 1; i <= n; ++i)
		fac[i] = mul(fac[i - 1], i);
	invfac[n] = fpow(fac[n], P - 2);
	for (int i = n - 1; i >= 0; --i)
		invfac[i] = mul(invfac[i + 1], i + 1);
	dp[0][0][0] = 1;
	bool flag = true;
	for (int i = 1; i <= n; ++i)
	{
		deg = read();
		flag &= (deg == 2);
		for (int j = 0; j < i; ++j)	
			for (int p = 0; p < 2; ++p) if (dp[i - 1][j][p])
			{
				int t = dp[i - 1][j][p];
				inc(dp[i][j][p], mul(t, invfac[deg - 1]));
				if (deg >= 2)
					inc(dp[i][j + 1][p], mul(t, invfac[deg - 2]));
				if (!p && deg >= 3)
					inc(dp[i][j + 1][p + 1], mul(t, invfac[deg - 3]));
			}
	}
	if (flag)
		ans = mul(invfac[2], fac[n - 1]);
	for (int k = 3; k < n; ++k)
		inc(ans, mul(mul(invfac[2], mul(fac[n - k - 1], fac[k - 1])), dp[n][k][1]));
	printf("%d\n", ans);
	return 0;
}
