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>
#include <cstring>

using namespace std;
typedef long long int LL;
const LL MOD(1000000000LL + 7LL);
const int Max_N(305);

void exgcd(const LL &a, const LL &b, LL &x, LL &y)
{
	if (b == 0LL)
		x = 1LL, y = 0LL;
	else
		exgcd(b, a % b, y, x), y -= x * (a / b);
}

inline LL inverse(const LL &a)
{
	LL invx, invy;
	exgcd(a, MOD, invx, invy);
	return (invx % MOD + MOD) % MOD;
}

inline LL Mult(const LL &a, const LL &b)
{
	return a * b % MOD;
}

int N, D[Max_N];
LL Fac[Max_N], Inv[Max_N];

void init()
{
	scanf("%d", &N);
	for (int i = 1;i <= N;++i)
		scanf("%d", D + i);
	Fac[0] = Inv[0] = 1LL;
	for (int i = 1;i <= N;++i)
	{
		Fac[i] = Mult(Fac[i - 1], i * 1LL);
		Inv[i] = inverse(Fac[i]);
	}
}

//假定我们已经得到一个环，大小为k（k >= 3），环上点要求度数为d1，d2，...，dk
//考虑一种新的prufer编码方式，不删除环上的点，只删除树上的点
//那么，树上的点出现次数必定为d-1，环上的点出现次数必定为d-2，并且序列的最后一个点是环上的点 
//编码总长度 = 西格玛(d - 1) - k = N - k 
//对答案的贡献为(k - 1)! / 2 * s! / xxx

inline void update(LL &a, const LL &b)
{
	(a += b) %= MOD;
}

LL Ans, F[Max_N][Max_N][2];
void dp()
{
	F[0][0][0] = 1LL;
	for (int i = 1;i <= N;++i)
		F[0][0][0] = Mult(F[0][0][0], Inv[D[i] - 1]);
	for (int i = 1;i <= N;++i)
	{
		for (int j = 0;j <= i - 1;++j)
			for (int c = 0;c <= 1;++c)
				F[i][j][c] = F[i - 1][j][c];
		if (D[i] >= 2)
			for (int j = 0;j <= i - 1;++j)
				for (int c = 0;c <= 1;++c)
					update(F[i][j + 1][c], Mult(F[i - 1][j][c], Mult(Fac[D[i] - 1], Inv[D[i] - 2])));
		if (D[i] >= 3)
			for (int j = 0;j <= i - 1;++j)
				update(F[i][j + 1][1], Mult(F[i - 1][j][0], Mult(Fac[D[i] - 1], Inv[D[i] - 3])));
	}
	for (int j = 3;j <= N - 1;++j)
		update(Ans, Mult(F[N][j][1], Mult(Mult(Fac[j - 1], inverse(2LL)), Fac[N - j - 1])));
	for (int i = 1;i <= N;++i)
		if (D[i] != 2)
			goto loop;
	update(Ans, Mult(Fac[N - 1], inverse(2LL)));
	loop :
	printf("%lld", Ans);
}

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