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 xx first
#define yy second
#define mp make_pair
#define pb push_back
#define mset(x, y) memset(x, y, sizeof x)
#define mcpy(x, y) memcpy(x, y, sizeof x)
using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

inline int Read()
{
	int x = 0, f = 1, c = getchar();
	for (; !isdigit(c); c = getchar())
		if (c == '-')
			f = -1;
	for (;  isdigit(c); c = getchar())
		x = x * 10 + c - '0';
	return x * f;
}

const int MAXN = 305;
const int mod = 1e9 + 7;

int n, a[MAXN], fac[MAXN], inv[MAXN], f[MAXN][MAXN][MAXN];

int main()
{
#ifdef wxh010910
	freopen("data.in", "r", stdin);
#endif
	n = Read(), fac[0] = fac[1] = inv[0] = inv[1] = 1;
	for (int i = 2; i <= n; i ++)
		fac[i] = 1LL * fac[i - 1] * i % mod, inv[i] = 1LL * (mod - mod / i) * inv[mod % i] % mod;
	bool sam = true;
	for (int i = 1; i <= n; i ++)
		inv[i] = 1LL * inv[i - 1] * inv[i] % mod, a[i] = Read(), sam &= a[i] == 2;
	if (sam)
		return printf("%d\n", 1LL * fac[n - 1] * inv[2] % mod), 0;
	f[0][0][0] = 1;
	for (int i = 0; i < n; i ++)
		for (int j = 0; j <= i; j ++)
			for (int k = 0; k <= n; k ++)
				if (f[i][j][k])
				{
					f[i + 1][j][k] = (f[i + 1][j][k] + f[i][j][k]) % mod;
					if (a[i + 1] >= 2)
						f[i + 1][j + 1][k + a[i + 1] - 2] = (1LL * (a[i + 1] - 1) * f[i][j][k] + f[i + 1][j + 1][k + a[i + 1] - 2]) % mod;
				}
	int ans = 0, cur = 1;
	for (int i = 1; i <= n; i ++)
		cur = 1LL * cur * inv[a[i] - 1] % mod;
	for (int i = 3; i < n; i ++)
		for (int j = 1; j <= n; j ++)
			if (f[n][i][j])
				ans = (1LL * j * fac[i - 1] % mod * f[n][i][j] % mod * fac[n - i - 1] % mod * inv[2] % mod * cur + ans) % mod;
	return printf("%d\n", ans), 0;
}
