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>
typedef long long ll;
#define mod 1000000007
ll gi(){
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))f^=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?x:-x;
}
std::mt19937 rnd(time(NULL));
#define rand rnd
#define pr std::pair<int,int>
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
template<class T>void cxk(T&a,T b){a=a>b?a:b;}
template<class T>void cnk(T&a,T b){a=a<b?a:b;}
#ifdef mod
int pow(int x,int y){
	int ret=1;
	while(y){
		if(y&1)ret=1ll*ret*x%mod;
		x=1ll*x*x%mod;y>>=1;
	}
	return ret;
}
template<class Ta,class Tb>void inc(Ta&a,Tb b){a=a+b>=mod?a+b-mod:a+b;}
template<class Ta,class Tb>void dec(Ta&a,Tb b){a=a>=b?a-b:a+mod-b;}
#endif
int d[100010],f[333][333][2],fact[310],ifact[310];
int main(){
#ifdef LOCAL
	freopen("in.in","r",stdin);
	//freopen("out.out","w",stdout);
#endif
	int n=gi(),mx=0;
	for(int i=1;i<=n;++i)cxk(mx,d[i]=gi());
	fact[0]=1;for(int i=1;i<=n;++i)fact[i]=1ll*fact[i-1]*i%mod;
	ifact[n]=pow(fact[n],mod-2);for(int i=n;i;--i)ifact[i-1]=1ll*ifact[i]*i%mod;
	if(mx==2)printf("%d\n",1ll*(mod+1>>1)*fact[n-1]%mod),exit(0);
	f[1][0][0]=1;
	for(int i=1;i<=n;++i){
		for(int j=0;j<i;++j)
			for(int k=0;k<2;++k)
				if(f[i][j][k]){
					inc(f[i+1][j][k],1ll*ifact[d[i]-1]*f[i][j][k]%mod);
					if(d[i]>=2)inc(f[i+1][j+1][k],1ll*ifact[d[i]-2]*f[i][j][k]%mod);
					if(!k&&d[i]>=3)inc(f[i+1][j+1][1],1ll*ifact[d[i]-3]*f[i][j][k]%mod);
				}
	}
	int ans=0;for(int i=3;i<n;++i)inc(ans,1ll*fact[n-i-1]*f[n+1][i][1]%mod*fact[i-1]%mod);
	printf("%d\n",1ll*ans*(mod+1>>1)%mod);
	return 0;
}
