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 mset(a, b) memset(a, b, sizeof(a))
#define mcpy(a, b) memcpy(a, b, sizeof(a))
using namespace std;
typedef long long LL;
const int N = 305;

template <typename T> inline void read(T &AKNOI) {
	T x = 0, flag = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-') flag = -1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	AKNOI = flag * x;
}

namespace ModCalculator {
	const int MOD = 1e9 + 7;
	inline void Inc(int &x, int y) {
		x += y; if (x >= MOD) x -= MOD;
	}
	inline void Dec(int &x, int y) {
		x -= y; if (x < 0) x += MOD;
	}
	inline int Add(int x, int y) {
		Inc(x, y); return x;
	}
	inline int Sub(int x, int y) {
		Dec(x, y); return x;
	}
	inline int Mul(int x, int y) {
		return 1LL * x * y % MOD;
	}
	inline int Ksm(int x, int k) {
		int ret = 1;
	   	for (; k; k >>= 1) {
		    if (k & 1) ret = Mul(ret, x);
		    x = Mul(x, x);
		}
		return ret;
	}
	inline int Inv(int x) {
		return Ksm(x, MOD - 2);
	}
}
using namespace ModCalculator;

int n, d[N];
int fac[N], finv[N];
int dp[N][N][2];

void init() {
	read(n);
	for (int i = 1; i <= n; ++i) {
		read(d[i]);
	}
	fac[0] = 1;
	for (int i = 1; i <= n; ++i) {
		fac[i] = Mul(fac[i - 1], i);
	}
	finv[n] = Inv(fac[n]);
	for (int i = n; i >= 1; --i) {
		finv[i - 1] = Mul(finv[i], i);
	}
}

void solve() {
	bool cir = 1;
	for (int i = 1; i <= n; ++i) {
		cir &= (d[i] == 2);
	}
	if (cir) {
		printf("%d\n", Mul(fac[n - 1], finv[2]));
		return;
	}
	dp[0][0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < i; ++j) {
			for (int k = 0; k < 2; ++k) {
				Inc(dp[i][j][k], Mul(dp[i - 1][j][k], finv[d[i] - 1]));
				if (d[i] > 1) {
					Inc(dp[i][j + 1][k], Mul(dp[i - 1][j][k], finv[d[i] - 2]));
				}
				if (!k && d[i] > 2) {
					Inc(dp[i][j + 1][1], Mul(dp[i - 1][j][k], finv[d[i] - 3]));
				}
			}
		}
	}
	int ans = 0;
	for (int i = 3; i < n; ++i) {
		Inc(ans, Mul(dp[n][i][1], Mul(fac[n - i - 1], Mul(fac[i - 1], finv[2]))));
	}
	printf("%d\n", ans);
}

int main() {
	init();
	solve();
	return 0;
}
