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

// duliuSYC

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int mod;

inline void Inc(int &x, int y) {
	x = x + y >= mod ? x + y - mod : x + y;
}

inline void Dec(int &x, int y) {
	x = x - y < 0 ? x - y + mod : x - y;
}

inline int Add(int x, int y) {
	return x + y >= mod ? x + y - mod : x + y;
}

inline int Sub(int x, int y) {
	return x - y < 0 ? x - y + mod : x - y;
}

inline int Pow(ll x, int y) {
	ll ret = 1;
	for (; y; y >>= 1, x = x * x % mod)
		if (y & 1) ret = ret * x % mod;
	return ret;
}

int fac[1000005], inv[1000005], ifac[1000005];

inline void Init() {
	int i;
	fac[0] = fac[1] = ifac[0] = ifac[1] = inv[1] = 1;
	for (i = 2; i <= 1000000; ++i) inv[i] = (ll)inv[mod % i] * (mod - mod / i) % mod;
	for (i = 2; i <= 1000000; ++i) {
		fac[i] = (ll)fac[i - 1] * i % mod;
		ifac[i] = (ll)ifac[i - 1] * inv[i] % mod;
	}
}

inline int C(int x, int y) {
	if (x < 0 || y < 0 || y > x) return 0;
	return (ll)fac[x] * ifac[y] % mod * ifac[x - y] % mod;
}

namespace Task1 {
	int n, cur, ans;
	
	inline void Solve() {
		int i, d;
		ans = 1;
		scanf("%d", &n);
		if (n == 1) {
			scanf("%d", &d);
			d ? puts("0") : puts("1");
			return;
		}
		for (i = 1; i <= n; ++i) {
			scanf("%d", &d);
			if (!d) {
				puts("0");
				return;
			}
			cur += d;
			ans = (ll)ans * ifac[d - 1] % mod;
		}
		if ((cur & 1) || cur / 2 != n - 1) {
			puts("0");
			return;
		}
		ans = (ll)ans * fac[cur - n] % mod;
		printf("%d\n", ans);
	}
}

namespace Task2 {
	int n, cur, ans, d[5005], f[305][305][305];

	/*
    int vis[5005];
	  
	inline void Calc(int tot, int sumd) {
		int i, ret;
		ret = fac[tot - 1], sumd -= tot << 1;
		if (tot != n && !sumd) return;
		if (tot == n) {
			Inc(ans, ret);
			return;
		}
		ret = (ll)ret * sumd % mod, --sumd;
		for (i = 1; i <= n; ++i)
			if (!vis[i]) {
				ret = (ll)ret * ifac[d[i] - 1] % mod;
				sumd += d[i] - 1;
			}
			else if (d[i] > 2) ret = (ll)ret * ifac[d[i] - 2] % mod;
		ret = (ll)ret * fac[sumd] % mod;
		Inc(ans, ret);
	}
	
	void Dfs(int x, int cnt, int sumd) {
		if (x > n) {
			if (cnt > 2) Calc(cnt, sumd);
		}
		else {
			if (d[x] > 1) {
				vis[x] = 1;
				Dfs(x + 1, cnt + 1, sumd + d[x]);
				vis[x] = 0;
			}
			Dfs(x + 1, cnt, sumd);
		}
	}
	*/
	
	inline void Calc300() {
		int i, j, k, sumd, ret, sum;
		f[0][0][0] = 1, sum = 0;
		for (i = 1; i <= n; ++i) {
			for (j = 0; j <= i; ++j)
				for (k = 0; k <= sum; ++k)
					f[i][j][k] = (ll)f[i - 1][j][k] * ifac[d[i] - 1] % mod;
			if (d[i] > 1) {
				for (j = 1; j <= i; ++j)
					for (k = 0; k <= sum; ++k)
						Inc(f[i][j][k + d[i] - 1], (ll)f[i - 1][j - 1][k] * ifac[d[i] - 2] % mod);
			}
			sum += d[i] - 1;
		}
		for (i = 3; i <= n; ++i)
			for (j = i; j <= n; ++j)
				if (f[n][i][j]) {
					sumd = j - i;
					ret = (ll)fac[i - 1] * f[n][i][j] % mod;
					if (i != n && !sumd) continue;
					if (i == n) {
						Inc(ans, ret);
						continue;
					}
					ret = (ll)ret * sumd % mod;
					sumd = sumd - 1 + sum - j;
					ret = (ll)ret * fac[sumd] % mod;
					Inc(ans, ret);
				}
		ans = (ll)ans * inv[2] % mod;
	}

	inline bool CheckSame() {
		int i;
		for (i = 2; i <= n; ++i) if (d[i] != d[i - 1]) return 0;
		return 1;
	}
	
	inline void Solve() {
		int i;
		scanf("%d", &n);
		if (n <= 2) {
			puts("0");
			return;
		}
		for (i = 1; i <= n; ++i) {
			scanf("%d", &d[i]);
			if (!d) {
				puts("0");
				return;
			}
			cur += d[i];
		}
		if ((cur & 1) || cur / 2 != n) {
			puts("0");
			return;
		}
		if (CheckSame()) ans = (ll)fac[n - 1] * inv[2] % mod;
		else Calc300();
		printf("%d\n", ans);
	}
}

namespace Task3 {
	int n, m, d, p[100005], ans, fa[100005], st[100005];

	inline int Find(int x) {
		return fa[x] == x ? x : fa[x] = Find(fa[x]);
	}

	inline int Find2(int x) {
		return st[x] == x ? x : st[x] = Find2(st[x]);
	}

	inline bool Check() {
		int i, j;
		for (i = 1; i < n; ++i)
			for (j = i + 1; j <= n; ++j)
				if (p[j] < p[i] && Find(p[j]) != Find(p[i])) return 0;
		for (i = 1; i <= n; ++i) st[i] = i;
		for (i = 1; i < n; ++i)
			for (j = i + 1; j <= n; ++j)
				if (p[j] < p[i] && Find2(p[j]) != Find2(p[i]))
					st[Find2(p[j])] = Find2(p[i]);
		for (i = 1; i < n; ++i)
			for (j = i + 1; j <= n; ++j)
				if (Find(i) == Find(j) && Find2(i) != Find2(j)) return 0;
		return 1;
	}
	
	inline void Solve() {
		int i, u, v;
		scanf("%d%d", &n, &m);
		for (i = 1; i <= n; ++i) p[i] = fa[i] = i;
		for (i = 1; i <= m; ++i) {
			scanf("%d", &d);
			if (!d) continue;
			scanf("%d", &u), --d;
			while (d) {
				scanf("%d", &v), --d;
				if (Find(u) != Find(v)) fa[Find(v)] = Find(u);
			}
		}
		do {
			if (Check()) ++ans;
		} while (next_permutation(p + 1, p + n + 1));
		printf("%d\n", ans % mod);
	}
}

int cas;

int main() {
    cas = 2, mod = 1e9 + 7;
	Init();
	if (cas == 1) Task1 :: Solve();
	else if (cas == 2) Task2 :: Solve();
	else Task3 :: Solve();
	return 0;
}