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>
int D[310][310][610], w[310], n, Mod = 1000000007, F[410], InvF[410], res;

int Pow(int a, int b) {
	int r = 1;
	while (b) {
		if (b & 1)r = 1ll * r*a%Mod;
		a = 1ll * a*a%Mod; b >>= 1;
	}
	return r;
}

int main() {
	int i, j, k, s = 0;
	scanf("%d", &n);
	for (i = 1; i <= n; i++)scanf("%d", &w[i]);
	F[0] = InvF[0] = 1;
	for (i = 1; i <= 400; i++) {
		F[i] = 1ll * F[i - 1] * i%Mod;
		InvF[i] = Pow(F[i], Mod - 2);
	}
	D[0][0][0] = 1;
	for (i = 1; i <= n; i++) {
		for (j = 0; j < i; j++) {
			for (k = 0; k <= s; k++) {
				D[i][j][k] = (D[i][j][k] + 1ll * D[i - 1][j][k] * InvF[w[i] - 1])%Mod;
				if (w[i] >= 2) D[i][j + 1][k + w[i] - 2] = (D[i][j + 1][k + w[i] - 2] + 1ll * D[i - 1][j][k] * InvF[w[i] - 2]) % Mod;
			}
		}
		if (w[i] >= 2)s += w[i] - 2;
	}
	for (i = 3; i <= n; i++) {
		for (j = 0; j <= s; j++) {
			if (i != n && j == 0)continue;
			int t = 1ll * D[n][i][j] * F[i - 1] % Mod * InvF[2] % Mod * F[j] % Mod;
			if (i == n) res = (res + t) % Mod;
			else res = (res + 1ll * t*F[n - i - 1]%Mod*InvF[j-1]) % Mod;
		}
	}
	printf("%d\n", res);
}