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<algorithm>

using namespace std;

const long long mod = 1000000007;

long long fact[660];
long long ifact[660];

long long dp[2][330][660];

int N;
int D[330];

void input(){
	scanf("%d", &N);
	for(int i = 0; i < N; ++i){
		scanf("%d", D + i);
	}
}

bool isAll2(){
	for(int i = 0; i < N; ++i){
		if(D[i] != 2) return false;
	}
	return true;
}

void chadd(long long &a, long long b){
	a += b;
	if(a > mod) a -= mod;
}

long long mul(long long a, long long b){
	return (a * b) % mod;
}


long long ex(long long a, long long e){
	if(e == 0) return 1;
	long long tmp = ex(a, e / 2);
	tmp = mul(tmp, tmp);
	if(e % 2 == 1) tmp = mul(tmp, a);
	return tmp;
}

long long inv(long long x){
	return ex(x, mod - 2);
}

long long C(int n, int k){
	long long num = fact[n];
	long long den = mul(ifact[k], ifact[n - k]);
	return mul(num, den);
}

void init(){
	fact[0] = 1;
	ifact[0] = 1;
	for(int i = 1; i < 660; ++i){
		fact[i] = mul(fact[i - 1], i);
		ifact[i] = mul(ifact[i - 1], inv(i));
	}
}

long long solve(){
	init();
	if(isAll2()){
		long long x = fact[N - 1];
		if(x % 2 == 0) return x / 2;
		return (x + mod) / 2;
	}
	int t = 0;
	dp[t][0][0] = 1;
	for(int i = 0; i < N; ++i){
		for(int j = 0; j < 330; ++j){
			for(int k = 0; k < 330; ++k){
				dp[1 - t][j][k] = 0;
			}
		}
		for(int j = 0; j <= i; ++j){
			for(int k = 0; k < 330; ++k){
				// non cycle
				chadd(dp[1 - t][j][k], mul(dp[t][j][k], ifact[D[i] - 1]));
				// cycle
				if(D[i] == 1) continue;
				long long coe = mul(fact[k], ifact[k + D[i] - 2]);
				coe = mul(coe, C(k + D[i] - 2, D[i] - 2));
				long long tmp = mul(dp[t][j][k], coe);
				chadd(dp[1 - t][j + 1][k + D[i] - 2], tmp);
			}
		}
		t = 1 - t;
	}
	long long ans = 0;
	for(int j = 3; j <= N; ++j){
		long long tmp2 = 0;
		for(int k = 1; k <= N; ++k){
			long long tmp = dp[t][j][k];
			tmp = mul(tmp, k);
			chadd(tmp2, tmp);
		}
		tmp2 = mul(tmp2, fact[j - 1]);
		tmp2 = mul(tmp2, fact[N - j - 1]);
		chadd(ans, tmp2);
		//printf("%d %lld\n", j, tmp2);
	}
	if(ans % 2 == 0) return ans / 2;
	return (ans + mod) / 2;
	return ans;
}

int main(){
	input();
	long long ans = solve();
	printf("%lld\n", ans);
	return 0;
}
