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:
/*************************************
 * @contest:      dwacon6th-prelims.
 * @user_name:    hkxadpall.
 * @time:         2020-01-11.
 * @language:     C++.
 * @upload_place: AtCoder.
*************************************/ 

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

typedef signed char          int8;
typedef unsigned char       uint8;
typedef short                int16;
typedef unsigned short      uint16;
typedef int                  int32;
typedef unsigned            uint32;
typedef long long            int64;
typedef unsigned long long  uint64;

template <typename Int>
inline Int read()       
{
    Int flag = 1;
    char c = getchar();
    while ((!isdigit(c)) && c != '-') c = getchar();
    if (c == '-') flag = -1, c = getchar();
    Int init = c & 15;
    while (isdigit(c = getchar())) init = (init << 3) + (init << 1) + (c & 15);
	return init * flag;
}

template <typename Int>
inline Int read(char &c)       
{
    Int flag = 1;
    c = getchar();
    while ((!isdigit(c)) && c != '-') c = getchar();
    if (c == '-') flag = -1, c = getchar();
    Int init = c & 15;
    while (isdigit(c = getchar())) init = (init << 3) + (init << 1) + (c & 15);
	return init * flag;
}

template <typename Int>
inline void write(Int x)
{
    if (x < 0) putchar('-'), x = ~x + 1;
    if (x > 9) write(x / 10);
    putchar((x % 10) | 48);
}  

template <typename Int>
inline void write(Int x, char nextch)
{
    write(x);
    putchar(nextch);
}

#define P 1000000007

int n, main_k;
int a[20 + 3];
long long fac[1000 + 3], invf[1000 + 3];
long long _f[2][1000 + 3];

long long fpow(long long a, int n, const long long p)
{
    long long res = 1;
    while (n) {
        if (n & 1) res = res * a % p;
        a = a * a % p;
        n >>= 1;
    }
    return res;
}

#define inv(x) fpow(x, P - 2, P)

int C_init()
{
    fac[0] = 1;
    invf[0] = 1;
    for (int i = 1; i <= n; i++) {
        fac[i] = fac[i - 1] * i % P;
        invf[i] = inv(fac[i]);
    }
    return 0;
}

long long C(int n, int m)
{
    static bool C_init_tag = !C_init();
    // printf("query C(%d, %d) ret = %lld.\n", n, m, fac[n] * invf[m] % P * invf[n - m] % P);
    return fac[n] * invf[m] % P * invf[n - m] % P;
}

#define f _f[(i) & 1]
#define g _f[((i) & 1) ^ 1]

int main()
{
    n = read<int>();
    main_k = read<int>();
    _f[0][0] = 1;
    for (int i = 1; i <= main_k; i++) {
        a[i] = read<int>();
        memset(f, 0, sizeof(f));
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k <= min(n - j, a[i]); k++) {
                // printf("f[%d + %d] from g[%d](= %d)\n", j, k, j, g[j]);
                f[j + k] = (f[j + k] + g[j] * C(n - j, k) % P * C(n - k, a[i] - k) % P) % P;
                // printf(" = %lld.\n------------------------------\n", f[j + k]);
            }
        }
        // printf("f = {");
        // for (int j = 0; j <= n; j++) {
        //     printf("%lld", f[j]);
        //     if (j < n) printf(", ");
        // }
        // printf("}\n");
    }
    write(_f[main_k & 1][n]);
    return 0;
}