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:
#include "bits/stdc++.h"
using namespace std;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr<<"hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x,y) (lower_bound(all(x),y)-x.begin())
#define ubd(x,y) (upper_bound(all(x),y)-x.begin())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return rng() % (y+1-x) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

using ll=long long; 
using ld=long double;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
using pi=pair<ll,ll>; using spi=pair<ll,pi>; using dpi=pair<pi,pi>; 

#define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (300006)
int main(){
	FAST
	ll n, k, mod=1e9+7;
	cin>>n>>k;
	vector<ll> A(k+1,0);
	FOR(i,1,k)cin>>A[i];
	vector<ll>f(n+1,0),inv(n+1,0);
	auto qexp=[&](ll x,ll e){ll sum=1;for(;e;e>>=1,x*=x,x%=mod)if(e&1)sum*=x,sum%=mod;return sum;};
	f[0]=inv[0]=1; FOR(i,1,n)f[i]=f[i-1]*i%mod,inv[i]=qexp(f[i],mod-2);
	vector<vector<ll>> C(n+1,vector<ll>(n+1,0));
	FOR(i,0,n)C[i][0]=1;
	FOR(i,1,n)FOR(j,1,n)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
	vector<vector<ll>> dp(k+1,vector<ll>(n+1,0));
	dp[0][n]=1;
	FOR(i,1,k){
		FOR(j,0,n){
			FOR(l,j,min(j+A[i],n)){
				dp[i][j] += dp[i-1][l] * C[l][l-j] % mod * 
					C[n-(l-j)][A[i]-(l-j)] % mod, 
				dp[i][j] %= mod;
			}
			// cerr<<i<<' '<<j<<": "<<dp[i][j]<<'\n';
		}
	}
	cout<<dp[k][0]<<'\n';
}