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>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstdlib>
#define cmax(a,b) (a<(b)?a=(b),1:0)
#define cmin(a,b) (a>(b)?a=(b),1:0)
#define dmin(a,b) ((a)<(b)?(a):(b))
#define dmax(a,b) ((a)>(b)?(a):(b))
#define regsiter register
#define CL fclose(stdin),fclose(stdout)
namespace io
{
	int F()
	{
		int n=0,F=1;
		char ch;
		while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		ch=='-'?F=0:n=ch-'0';
		while((ch=getchar())>='0'&&ch<='9')n=(n<<1)+(n<<3)+ch-'0';
		return F?n:-n;
	}
	long long G()
	{
		long long n=0,F=1;
		char ch;
		while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		ch=='-'?F=0:n=ch-'0';
		while((ch=getchar())>='0'&&ch<='9')n=(n<<1)+(n<<3)+ch-'0';
		return F?n:-n;
	}
}
int d[333];
const int M=1000000007;
int f[2][333][666];
int fac[333];
int invf[333];
int ex(int b,int e)
{
	int ans=1;
	for(;e;e>>=1,b=(long long)b*b%M)
		if(e&1)ans=(long long)ans*b%M;
	return ans;
}
int main()
{
	int n=io::F();
	for(register int i=1;i<=n;++i)d[i]=io::F();
	fac[0]=1;
	for(register int i=1;i<=n;++i)fac[i]=(long long)fac[i-1]*i%M;
	int fl=1;
	for(register int i=1;i<=n;++i)if(d[i]!=2)fl=0;
	if(fl)
	{
		printf("%lld\n",fac[n-1]*(long long)(M+1>>1)%M);
		return 0;
	}
	invf[n]=ex(fac[n],M-2);
	for(register int i=n-1;i>=0;--i)invf[i]=(i+1)*(long long)invf[i+1]%M;
	int(*x)[666]=f[0],(*y)[666]=f[1];
	f[0][0][0]=1;
	for(register int i=1;i<=n;++i,std::swap(x,y))
	{
		for(register int j=0;j<=i;++j)
			for(register int k=0;k<=n+n;++k)
			{
				y[j][k]=x[j][k]*(long long)invf[d[i]-1]%M;
				if(d[i]>=2&&j>=1&&k+2>=d[i])y[j][k]=(y[j][k]+x[j-1][k-d[i]+2]*(long long)invf[d[i]-2])%M;				
			}
	}
	#define register
	int ans=0;
	for(register int i=3;i<n;++i)
		for(register int j=1;j<=n+n;++j)
			ans=(ans+(long long)x[i][j]*fac[n-i-1]%M*fac[i-1]%M*invf[j-1]%M*invf[2]%M*fac[j]%M)%M;
	printf("%d\n",ans);
	return 0;
}


