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
/*
考虑建立虚拟根 R 以后造 prufer 序列（和3776一样）
前 n-s-1 位随便，第 n-s 位是根节点，第 n-s+1 ~ n-1 位都是 R。
直接 dp 一下每个点的决策：
1、不作为根
2、作为根但是不填到 n-s 位去。 
3、作为根且搞定第 n-s 位。 
*/
#include<cstdio>

const int N = 5004, mod = 1000000007;

int n, ans, inv[N], fac[N], ifac[N], F[N][2];

int main()
{
	scanf("%d", &n);
	fac[0] = fac[1] = ifac[0] = ifac[1] = inv[1] = 1;
	for(int i = 2; i <= n; ++i)
	{
		fac[i] = 1ll * i * fac[i - 1] % mod;
		inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
		ifac[i] = 1ll * ifac[i - 1] * inv[i] % mod;
	}
	F[0][0] = 1;
	for(int i = 1, d; i <= n; ++i)
	{
		scanf("%d", &d);
		for(int j = i - 1; ~j; --j)
		{
			if(d >= 2)
				F[j + 1][0] = (F[j + 1][0] + 1ll * F[j][0] * ifac[d - 2]) % mod,
				F[j + 1][1] = (F[j + 1][1] + 1ll * F[j][1] * ifac[d - 2]) % mod;
			if(d >= 3)
				F[j + 1][1] = (F[j + 1][1] + 1ll * F[j][0] * ifac[d - 3]) % mod;
			F[j][0] = 1ll * F[j][0] * ifac[d - 1] % mod;
			F[j][1] = 1ll * F[j][1] * ifac[d - 1] % mod;
		}
	}
	if(!F[1][1])
		ans = 1ll * fac[n - 1] * inv[2] % mod;
	else for(int j = 3; j < n; ++j)
		ans = (ans + 1ll * F[j][1] * fac[n - j - 1] % mod * fac[j - 1] % mod * inv[2]) % mod;
	printf("%d", ans);
	return 0;
}
