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:
// / #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
 
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <cassert>
#include <unordered_set>
#include <unordered_map>
#include <set>
#include <map>
#include <queue>
#include <random>
#include <bitset>
#include <time.h>
#include <stack>
#include <sstream>
#include <regex>
 
#define prev asasddlsa
#define rank aljds
 
using namespace std;
 
typedef long long ll;
typedef long double dbl;

// mt19937 mrand(random_device{} ());
// int rnd(int x = INT_MAX) {
//     return mrand() % x;
// }

template<typename T>
void print(const vector<T>& s){
    for (auto x : s)
        cout << x << ' ';
    cout << endl;
}
 
template<class T>
void print(const T* s, int n){
    for (int i = 0; i < n; i++){
        cout << s[i] << ' ';
    }
    cout << endl;
}
 
template<class T>
void print(vector<vector<T>> s){
    for (int i = 0; i < s.size(); i++)
        print(s[i]);
}

const int mod = 1e9 + 7;

ll power(ll a, ll n){
    ll res = 1;
    while (n){
        if (n & 1)
            res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

ll inv(ll a){
    return power(a, mod - 2);
}

const int maxn = 1e3 + 7;

ll fact[maxn], inv_fact[maxn];

ll cnk(int n, int k){
    if (k > n)
        return 0;
    return fact[n] * inv_fact[k] % mod * inv_fact[n - k] % mod;
}

ll inv_cnk(int n, int k){
    assert(n >= k);
    return fact[k] * fact[n - k] % mod * inv_fact[n] % mod;
}

ll dp[maxn];

int main(){
    srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    fact[0] = inv_fact[0] = 1;
    for (int i = 1; i <= n; i++){
        fact[i] = fact[i - 1] * i % mod;
        inv_fact[i] = inv_fact[i - 1] * inv(i) % mod;
    }
    dp[0] = 1;
    ll mult = 1;
    for (int i = 0; i < k; i++){
        int a;
        cin >> a;
        // print(dp, n + 1);
        for (int j = n; j > 0; j--){
            for (int l = 1; l <= min(j, a); l++){
                ll coef = cnk(n - l, a - l) * cnk(j, l) % mod * inv_cnk(n, a) % mod;
                // if (i == 1 && j == n){
                //     cout << "coef: " << l << " " << coef << ' ' << dp[j - l] << endl;
                //     cout << cnk(n - l, a - l) << ' ' << cnk(j, l) << ' ' << inv_cnk(n, a) << endl;
                // }
                dp[j] = (dp[j] + dp[j - l] * coef) % mod;
                // if (i == 1 && j == n)
                    // cout << dp[n] << endl;
            }
            // print(dp, n + 1);
        }
        // print(dp, n + 1);
        mult = mult * cnk(n, a) % mod;
    }
    cout << dp[n] * mult % mod << endl;
    return 0;
}