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<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
ll mod = 1000000007;
#define SIZE 100000
ll inv[SIZE + 1];
ll kai[SIZE + 1];
ll invkai[SIZE + 1];
void invinit()
{
	inv[1] = 1;
	for (int i = 2; i <= SIZE; i++)
	{
		inv[i] = mod - (mod / i)*inv[mod%i] % mod;
	}
	kai[0] = invkai[0] = 1;
	for (int i = 1; i <= SIZE; i++)
	{
		kai[i] = kai[i - 1] * i%mod;
		invkai[i] = invkai[i - 1] * inv[i] % mod;
	}
}
ll com(ll a, ll b)
{
	if (b < 0 || a < b)return 0;
	return (invkai[b] * invkai[a - b]) % mod*kai[a] % mod;
}
ll po(ll a, ll b)
{
	if (b == 0)return 1;
	ll z = po(a, b / 2);
	z = z*z%mod;
	if (b & 1)z = z*a%mod;
	return z;
}
ll invv(ll a)
{
	return po(a, mod - 2);
}
int d[500];
ll dp[301][301][301];
int main()
{
	invinit();
	int num;
	scanf("%d", &num);
	int mini = 100;
	for (int i = 0; i < num; i++)scanf("%d", &d[i]), mini = min(mini, d[i]);
	if (mini == 2)
	{
		printf("%lld\n", kai[num - 1] * invv(2) % mod);
		return 0;
	}
	dp[0][0][0] = 1;
	for (int i = 0; i < num; i++)
	{
		for (int j = 0; j <= i; j++)
		{
			for (int k = 0; k <= num; k++)
			{
				dp[i + 1][j][k] = (dp[i + 1][j][k] + dp[i][j][k] * invkai[d[i] - 1]) % mod;
				if (d[i] >= 2)dp[i + 1][j + 1][k + d[i] - 2] = (dp[i + 1][j + 1][k + d[i] - 2] + dp[i][j][k] *invkai[d[i] - 2]) % mod;
			}
		}
	}
	ll ans = 0;
	for (int i = 3; i <= num - 1; i++)
	{
		for (int j = 0; j <= num; j++)
		{
			ans += dp[num][i][j] * kai[num - i - 1] % mod*j%mod*kai[i - 1]%mod*invv(2);
			ans %= mod;
		}
	}
	printf("%lld\n", ans);
}