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 <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#define m_p make_pair
#define sz(x) (int)x.size()
#define out(x) cerr<<#x<<" = "<<x<<" "
#define outln(x) cerr<<#x<<" = "<<x<<endl
#define outarr(x,l,r) cerr<<#x"["<<l<<"-"<<r<<"] = "; for (int _i=l;_i<=r;++_i) cerr<<x[_i]<<" ";cerr<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define gc() getchar()
//char buf[1<<23],*p1=buf,*p2=buf;
//#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
template <class T> void read(T &x)
{
    x=0; char c=gc(); int flag=0;
    while (c<'0'||c>'9') flag|=(c=='-'),c=gc();
    while (c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=gc();
    if (flag) x=-x;
}
template <class T> T _max(T a,T b){return a>b ? a : b;}
template <class T> T _min(T a,T b){return a<b ? a : b;}
template <class T> bool checkmax(T &a,T b){return b>a ? a=b,1 : 0;}
template <class T> bool checkmin(T &a,T b){return b<a ? a=b,1 : 0;}
const int mod=1000000000+7,N=305,inv2=(mod+1)/2;
int Add(int a,int b){a+=b; return a>=mod ? a-mod : a;}
int Sub(int a,int b){a-=b; return a>=0 ? a : a+mod;}
int Mul(int a,int b){return 1LL*a*b%mod;}
void add(int &a,int b){a=Add(a,b);}
void sub(int &a,int b){a=Sub(a,b);}
void mul(int &a,int b){a=Mul(a,b);}
int qpow(int x,int y)
{
	int ans=1;
	while (y)
	{
		if (y&1) mul(ans,x);
		mul(x,x);
		y>>=1;
	}
	return ans;
}

int n,deg[N];
int dp[N][N][N<<1];
int fac[N],inv_fac[N];
void init()
{
	read(n);
	for (int i=1;i<=n;++i)
	{
		read(deg[i]);
	}
	fac[0]=1;
	for (int i=1;i<=n;++i)
	{
		fac[i]=Mul(fac[i-1],i);
	}
	inv_fac[n]=qpow(fac[n],mod-2);
	for (int i=n-1;i>=0;--i)
	{
		inv_fac[i]=Mul(inv_fac[i+1],i+1);
	}
	sort(deg+1,deg+n+1,greater<int>());
	//outarr(deg,1,n);
	dp[1][0][0]=1;
	dp[1][1][deg[1]]=deg[1]-1;
	for (int i=2;i<=n;++i)
	{
		for (int j=0;j<=i;++j)
		{
			for (int q=0;q<=n+n;++q)
			{
				dp[i][j][q]=dp[i-1][j][q];
				if (deg[i]>=2&&j>=1&&q>=deg[i]) 
				{
					add(dp[i][j][q],Mul(dp[i-1][j-1][q-deg[i]],deg[i]-1));
				}
				//cout<<i<<" "<<j<<" "<<q<<" "<<dp[i][j][q]<<endl;
			}
		}
	}
}

void solve()
{
	int multi=1;
	for (int i=1;i<=n;++i)
	{
		mul(multi,inv_fac[deg[i]-1]);
	}
	//outln(multi);
	int ans=Mul(dp[n][n][n+n],Mul(fac[n-1],inv2));
	for (int loop=3;loop<n;++loop)
	{
		for (int sum_deg=loop*2;sum_deg<=n+n;++sum_deg)
		{
			int tmp=Mul(fac[loop-1],Mul(inv2,fac[n-loop-1]));
			mul(tmp,multi);
			//cout<<loop<<" "<<sum_deg<<" "<<tmp<<" "<<dp[n][loop][sum_deg]<<endl;
			mul(tmp,dp[n][loop][sum_deg]);
			mul(tmp,sum_deg-loop*2);
			add(ans,tmp);
		}
	}
	printf("%d\n",ans);
} 
       
#undef int
int main()
{
	init();
	solve();
    return 0;
}
