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<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=500000004;
const double EPS=1e-6;
const double PI=acos(-1.0);
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
int d[310];
long long inv[110000];
long long fact[110000];
long long finv[110000];
long long dp[2][310][610];
int main(){
	inv[1]=fact[0]=finv[0]=1;
	for(int i=2;i<110000;i++)inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	for(int i=1;i<110000;i++){
		fact[i]=fact[i-1]*i%mod;
		finv[i]=finv[i-1]*inv[i]%mod;
	}
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%d",d+i);
	std::sort(d,d+a);
	long long ret=0;
	dp[0][0][0]=1;
	for(int i=0;i<a;i++){
	//	printf("%d\n",d[i]);
		int t=i%2;
		for(int j=0;j<=a;j++)for(int k=0;k<=2*a;k++)dp[!t][j][k]=0;
		for(int j=0;j<a;j++){
			for(int k=0;k<=2*a;k++){
				if(!dp[t][j][k])continue;
		//		printf("%d %d %d: %lld\n",i,j,k,dp[t][j][k]);
				dp[!t][j][k]=(dp[!t][j][k]+dp[t][j][k]*finv[d[i]-1])%mod;
				if(d[i]>=2)dp[!t][j+1][k+d[i]-2]=(dp[!t][j+1][k+d[i]-2]+dp[t][j][k]*finv[d[i]-2])%mod;
			}
		}
	}
 
	int t=a%2;
	for(int i=3;i<=a;i++){
		for(int j=0;j<=a*2;j++){
	
	//		if(dp[t][i][j])printf("%d %d: %lld\n",i,j,dp[t][i][j]);
			if((a-i&&j==0))continue;
			if(j==0){
				ret=(ret+dp[t][i][j]*fact[i]%mod*inv[i]%mod*inv[2])%mod;
				continue;
			}
			//if(dp[t][i][j])printf("%d %d: %lld\n",i,j,fact[a-i+1-2]*dp[t][i][j]%mod*finv[j-1]%mod*fact[i]%mod*inv[i]%mod*inv[2]%mod);
			if(dp[t][i][j])ret=(ret+fact[a-i+1-2]*dp[t][i][j]%mod*fact[j]%mod*finv[j-1]%mod*fact[i]%mod*inv[i]%mod*inv[2])%mod;
		}}
	
	printf("%lld\n",ret);
}