Problem: There are N children, numbered 1,2,\ldots,N. In the next K days, we will give them some cookies. In the i-th day, we will choose a_i children among the N with equal probability, and give one cookie to each child chosen. (We make these K choices independently.)

Let us define the happiness of the children as c_1 \times c_2 \times \ldots \times c_N, where c_i is the number of cookies received by Child i in the K days. Find the expected happiness multiplied by \binom{N}{a_1} \times \binom{N}{a_2} \times \ldots \times \binom{N}{a_K} (we can show that this value is an integer), modulo (10^{9}+7).

Constraints

* 1 \leq N \leq 1000
* 1 \leq K \leq 20
* 1 \leq a_i \leq N

Input

Input is given from Standard Input in the following format:


N K
a_1 a_2 \ldots a_K


Output

Print the answer.

Examples

Input

3 2
3 2


Output

12


Input

856 16
399 263 665 432 206 61 784 548 422 313 848 478 827 26 398 63


Output

337587117

Solution (in CPP):

Solution:
// Crt. 2020-01-13  15:18:08

// C: Cookie Distribution
// 思维好题..
// 直接计算并不好算.考虑转化一下方法.
// 由于是将所有的c_i乘起来,所以我们可以考虑它的组合意义,即对于所有人,我选一个cookie作为它的`chosen cookie`,然后所有选择的方案数.
// 那么我们可以枚举每一天,有多少人将这一天分配的cookie作为他的`chosen cookie`,设有x_i个.
// 那么其他的反正也没有被选中,所以我可以随便给其他人,并且不用担心会有一个人拿到同一天的两个,方案数为:$\pro_{i=1}^{k}{C_{n-x_i}^{a_i-x_i}}$.
// 就可以用DP来解决.我们可以先将人的标号去掉,设f[i][j]表示前i天选了j个cookie.
// 最后的答案乘上$N!/\{\pro{x!}}$即可.

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define N 1003
using namespace std;
const int Mod = 1e9 + 7;

inline int MOD(int x) {
    return x >= Mod ? x - Mod : x;
}

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, K, a[N], f[30][N], fac[N], ifac[N];

inline int C(int x, int y) {
    return x < y ? 0 : 1ll * fac[x] * ifac[y] % Mod * ifac[x - y] % Mod;
}

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

    cin >> n >> K;
    for (int i = 1; i <= K; ++i)
        scanf ("%d", a + i);

    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;

    f[0][0] = 1;
    for (int i = 1; i <= K; ++i)
        for (int j = 0; j <= n; ++j) if (f[i - 1][j])
            for (int k = 0; j + k <= n && k <= a[i]; ++k)
                f[i][j + k] = (1ll * f[i - 1][j] * C(n - k, a[i] - k) % Mod * ifac[k] + f[i][j + k]) % Mod;

    cout << 1ll * f[K][n] * fac[n] % Mod << endl;

	return 0;
}