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 lint;
const int maxn = 305, mod = 1e9 + 7, inv = (mod + 1) / 2;

int n, d[maxn], f[maxn][maxn][2], fac[maxn], ifac[maxn];

inline int gi()
{
	char c = getchar();
	while (c < '0' || c > '9') c = getchar();
	int sum = 0;
	while ('0' <= c && c <= '9') sum = sum * 10 + c - 48, c = getchar();
	return sum;
}

inline int inc(int a, int b) {return a + b >= mod ? a + b - mod : a + b;}
inline int mul(int a, int b) {return (lint)a * b % mod;}

int main()
{
	n = gi();
	int flg = 1;
	for (int i = 1; i <= n; ++i) d[i] = gi(), flg &= d[i] == 2;

	fac[0] = 1;
	for (int i = 1; i <= n; ++i) fac[i] = mul(fac[i - 1], i);
	ifac[0] = ifac[1] = 1;
	for (int i = 2; i <= n; ++i) ifac[i] = mul(mod - mod / i, ifac[mod % i]);
	for (int i = 1; i <= n; ++i) ifac[i] = mul(ifac[i - 1], ifac[i]);

	if (flg) return printf("%d\n", n == 2 ? 1 : mul(fac[n - 1], inv)), 0;
	
	f[0][0][0] = 1;
	for (int i = 1; i <= n; ++i)
		for (int j = 0; j <= i; ++j)
			for (int k = 0; k <= 1; ++k) {
				f[i][j][k] = f[i - 1][j][k];
				if (d[i] >= 2 && j > 0) f[i][j][k] = inc(f[i][j][k], mul(f[i - 1][j - 1][k], d[i] - 1));
				if (d[i] >= 3 && j > 0 && k) f[i][j][k] = inc(f[i][j][k], mul(mul(f[i - 1][j - 1][0], d[i] - 1), d[i] - 2)); 
			}

	int ans = 0;
	for (int i = 3; i <= n; ++i) ans = inc(ans, mul(f[n][i][1], mul(fac[n - i - 1], mul(fac[i - 1], inv))));
	for (int i = 1; i <= n; ++i) ans = mul(ans, ifac[d[i] - 1]);

	printf("%d\n", ans);
	
	return 0;
}
