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
// 2020 0517 1910
// 要知道 prufer 序.
// 要会计数.
#include <bits/stdc++.h>
#define N 333
using namespace std;
const int mod = 1e9 + 7;

inline int fsp(int x, int p = mod - 2) {
    int res = 1;
    while (p) {
        if (p & 1) res = 1ll * res * x % mod;
        x = 1ll * x * x % mod, p >>= 1;
    }
    return res;
}

int n, d[N], f[N][N][2], fac[N], ifac[N];

inline int cir(int x) {
    return 1ll * fac[x - 1] * ((mod + 1) / 2) % mod;
}

int main() {
#ifdef isLOCAL
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
#endif

    n = 300;
    for (int i = fac[0] = 1; i <= n; ++i)
        fac[i] = 1ll * fac[i - 1] * i % mod;
    ifac[n] = fsp(fac[n]);
    for (int i = n; i >= 1; --i)
        ifac[i - 1] = 1ll * ifac[i] * i % mod;

    cin >> n;
    int flag = 1;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", d + i);
        if (d[i] != 2) flag = 0;
    }
    if (flag) return cout << cir(n) << endl, 0;

    f[0][0][0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= i; ++j) {
            for (int k = 0; k <= 1; ++k) {
                int &t = f[i][j][k];
                t = (t + 1ll * f[i - 1][j][k] * ifac[d[i] - 1]) % mod;
                if (j && d[i] >= 2)
                    t = (t + 1ll * f[i - 1][j - 1][k] * ifac[d[i] - 2]) % mod;
            }
            if (j && d[i] >= 3)
                f[i][j][1] = (f[i][j][1] + 1ll * f[i - 1][j - 1][0] * ifac[d[i] - 3]) % mod;
        }

    long long ans = 0;
    for (int i = 3; i < n; ++i)
        ans = (ans + 1ll * f[n][i][1] * fac[n - i - 1] % mod * cir(i)) % mod;
    cout << ans << endl;
    return 0;
}