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 <cstring>

typedef unsigned long long	ull;
const size_t			MaxN = 5005;
const int			Mod = 1000000007;

int fexp(int base, int exp)
{
	int	res = 1;
	for(; exp; exp >>= 1, base = (ull) base * base % Mod)
		if(exp & 1)
			res = (ull) res * base % Mod;
	return res;
}

int	N, D[MaxN];
int	Fac[MaxN], Inv[MaxN], F[MaxN][2];

bool all2()
{
	for(int i = 1; i <= N; ++i)
		if(D[i] != 2)
			return false;
	return true;
}

int main()
{
	scanf("%d", &N);
	for(int i = 1; i <= N; ++i)
		scanf("%d", D + i);

	Fac[0] = 1;
	for(int i = 1; i <= N; ++i)
		Fac[i] = (ull) Fac[i - 1] * i % Mod;
	Inv[N] = fexp(Fac[N], Mod - 2);
	for(int j = N - 1; ~j; --j)
		Inv[j] = (ull) Inv[j + 1] * (j + 1) % Mod;
	int	inv2 = Inv[2];

	if(all2())
		printf("%llu\n", (ull) Fac[N - 1] * inv2 % Mod);
	else {
		F[0][0] = 1;
		for(int i = 1; i <= N; ++i) {
			for(int j = i - 1; ~j; --j) {
				if(F[j][0]) {
					if(D[i] >= 2)
						F[j + 1][0] = (F[j + 1][0] + (ull) F[j][0] * Inv[D[i] - 2]) % Mod;
					if(D[i] >= 3)
						F[j + 1][1] = (F[j + 1][1] + (ull) F[j][0] * Inv[D[i] - 3]) % Mod;
					F[j][0] = (ull) F[j][0] * Inv[D[i] - 1] % Mod;
				}
				if(F[j][1]) {
					if(D[i] >= 2)
						F[j + 1][1] = (F[j + 1][1] + (ull) F[j][1] * Inv[D[i] - 2]) % Mod;
					F[j][1] = (ull) F[j][1] * Inv[D[i] - 1] % Mod;
				}
			}
		}
		int	ans = 0;
		for(int i = 3; i <= N; ++i)
			ans = (ans + (ull) F[i][1] * Fac[N - i - 1] % Mod * Fac[i - 1] % Mod * inv2) % Mod;
		printf("%d\n", ans);
	}

	return 0;
}
