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 <iostream>
#include <algorithm>
#define int long long
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;

int powmod(int a, int n, int mod) {
	if (a >= mod) a %= mod;
	if (n == 0) return 1;
	if (n % 2 == 0) return powmod((a * a) % mod, n / 2, mod);
	return (a * powmod(a, n - 1, mod)) % mod;
}

int mod = 1000000007;
int n, k;
int a[20];
int dp[21][1001];
int fact[10000];
int finv[10000];

int comb(int n, int k) {
	return fact[n] * finv[k] % mod * finv[n - k] % mod;
}

signed main() {
	int i, j, l;
	
	fact[0] = 1;
	finv[0] = 1;
	for (i = 1; i < 10000; i++) {
		fact[i] = (i * fact[i - 1]) % mod;
		finv[i] = powmod(fact[i], mod - 2, mod);
	}
	
	cin >> n >> k;
	rep(i, k) cin >> a[i];
	
	dp[0][0] = 1;
	rep(i, k) {
		rep(j, n + 1) {
			rep(l, min(n - j, a[i]) + 1) {
				dp[i + 1][j + l] += dp[i][j] * comb(n - j, l) % mod * comb(n - l, a[i] - l);
				dp[i + 1][j + l] %= mod;
			}
		}
	}
	
	cout << dp[k][n] << endl;
	return 0;
}

//Aij = i日目に子供jがクッキーをもらった1, もらってない0
//とし、ΣScore(A) (all A)を求める問題。Score(A)が積の形で都合が悪い. 
// (本番はcnt[i] = i個クッキーを貰った子供の数とし、Score(A) = Πi ^ cnt[i]と言い換え、各「配列cnt」が何回現れるかを考察したが、筋が悪かった）
//こういうときは、「何かの個数」に言い換えられると嬉しい。
//このテクは、ARCの過去問「Convex Score」にもある。
//
//重要な考察：Score(A)は、「各子供から1つずつクッキーを選ぶ方法の個数」と同じ。
//Aを作ったあと、各子供から選んだクッキー（マス）に印をつけてみる。つまり、次のような行列を考える
//B = i日目に子供jがクッキーをもらいかつ選んだ2, もらったが選ばず1, もらわず0
//Bの作り方：Aを作った後、Aの各列の「1」を1つずつ選び、〇をつける。〇をつけた1を2に書き換えたものをBとする。
//このとき、各Aごとに作れるBはScore(A)個ある。もちろんAが違えば対応するBも異なる。
//よって、作れるBの個数が答えになる。
//
//作れるBの制約は、
//・Bij in {0, 1, 2}
//・任意のiについて、#{j | Bij >= 1} = a[i]
//・任意のjについて、#{i | Bij = 2} = 1
//と書ける。これらを全て満たす行列（表）を数えればよいことが分かった。
//
//ここからは典型で、i=1,2,…ごとに1行ずつ決めていくだけ。
//・「2」を入れた列には{0, 1}しか入れることができない
//というのが特別な制約で、「2」を入れた列数jが大事そう。
//・dp[i][j] = i日決めた. 2を入れた列数がj個. 何通り？
//というdpを考える。遷移として、
//・2を新たにl個追加する場合を考える。
//　・この場合、dp[i][j]からは、dp[i + 1][j + l]に「必ず遷移する」ので、立式可能。
//　・まず、j + l <= N かつ l <= a[i]を満たす必要がある.
//	・このとき、2を入れる方法は、N - j列のうちからl列を選ぶ方法なので、comb(N - j, l)通り.
//　・その各々について、残るN - l列からa[i] - l列には1を、それ以外の列には0を入れる方法が、comb(N - l, a[i] - l)通り.
//・よって、dp[i][j]からdp[i + 1][j + l]には、各々comb(N - j, l) × comb(N - l, a[i] - l)通りの遷移がある。
//あとはi, j, lをループで回せば良い。計算量はO(KN^2)。