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;

const int N = 305;
const int mod = 1000000007;
using Dp = array<array<int, N>, 2 * N>;

void add(int &x, int y) {
	x += y;
	if (x >= mod) x -= mod;	
}

int mul(int x, int y) {
	return (long long) x * y % mod;
}

int pw(int x, int y) {
	int ans = 1;
	for (; y > 0; y >>= 1, x = mul(x, x)) {
		if (y & 1) ans = mul(ans, x);
	}		
	return ans;
}

int deg[N];
int fact[N];
int ifact[N];

void precalc() {
	fact[0] = 1;
	for (int i = 1; i < N; ++i) {
		fact[i] = mul(fact[i - 1], i);
	}
	ifact[N - 1] = pw(fact[N - 1], mod - 2);
	for (int i = N - 1; i > 0; --i) {
		ifact[i - 1] = mul(ifact[i], i);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	precalc();
	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> deg[i];
	}
	Dp f{};
	f[0][0] = 1;
	int sumDeg = 0;
	for (int i = 1; i <= n; ++i) {
		Dp nf{};
		for (int nv = 0; nv <= i - 1; ++nv) {
			for (int sd = 0; sd <= sumDeg; ++sd) {
				add(nf[nv][sd], mul(f[nv][sd], ifact[deg[i] - 1]));
				if (deg[i] > 1) {
					add(nf[nv + 1][sd + deg[i] - 2], mul(f[nv][sd], ifact[deg[i] - 2]));
				}
			}
		}
		f = nf;
		sumDeg += max(0, deg[i] - 2);
	}
	int ans = 0;
	for (int nv = 3; nv < n; ++nv) {
		for (int sd = 1; sd <= sumDeg; ++sd) {
			int coef = mul(fact[n - nv - 1], fact[sd]);
			coef = mul(coef, ifact[sd - 1]);
			coef = mul(coef, fact[nv - 1]);
			add(ans, mul(coef, f[nv][sd]));
		}
	}
	bool flag = true;
	for (int i = 1; i <= n; ++i) {
		if (deg[i] != 2) {
			flag = false;
			break;
		}
	}
	if (flag) {
		add(ans, fact[n - 1]);
	}
	cout << mul(ans, (mod + 1) / 2) << "\n";
	return 0;
}