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;

#define CO const
#define IN inline
typedef long long int64;

template<class T> IN T read(){
	T x=0,w=1;char c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-') w=-w;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	return x*w;
}
template<class T> IN T read(T&x){
	return x=read<T>();
}

CO int mod=1e9+7,i2=(mod+1)/2;
IN int add(int a,int b){
	return (a+=b)>=mod?a-mod:a;
}
IN int mul(int a,int b){
	return (int64)a*b%mod;
}
IN int fpow(int a,int b){
	int ans=1;
	for(;b;b>>=1,a=mul(a,a))
		if(b&1) ans=mul(ans,a);
	return ans;
}

CO int N=310;
int fac[N],ifac[N];
int d[N],f[N][N][2];

int main(){
	int n=read<int>();
	fac[0]=1;
	for(int i=1;i<=n;++i) fac[i]=mul(fac[i-1],i);
	ifac[n]=fpow(fac[n],mod-2);
	for(int i=n-1;i>=0;--i) ifac[i]=mul(ifac[i+1],i+1);
	for(int i=1;i<=n;++i) read(d[i]);
	f[0][0][0]=1;
	for(int i=0;i<n;++i)for(int j=0;j<=i;++j){
		f[i+1][j][0]=add(f[i+1][j][0],mul(f[i][j][0],ifac[d[i+1]-1]));
		f[i+1][j][1]=add(f[i+1][j][1],mul(f[i][j][1],ifac[d[i+1]-1]));
		if(d[i+1]<2) continue;
		f[i+1][j+1][0]=add(f[i+1][j+1][0],mul(f[i][j][0],ifac[d[i+1]-2]));
		f[i+1][j+1][1]=add(f[i+1][j+1][1],mul(f[i][j][1],ifac[d[i+1]-2]));
		if(d[i+1]<3) continue;
		f[i+1][j+1][1]=add(f[i+1][j+1][1],mul(f[i][j][0],ifac[d[i+1]-3]));
	}
	int ans=0;
	for(int j=3;j<n;++j)
		ans=add(ans,mul(f[n][j][1],mul(fac[n-j-1],mul(fac[j-1],i2))));
	if(n>=3) ans=add(ans,mul(f[n][n][0],mul(fac[n-1],i2)));
	printf("%d\n",ans);
	return 0;
}
