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:
/*
	期望乘上那个组合数就是所有方案下的答案了对吧
	首先原问题可以转化成这样一个问题
	每一个人可以从拥有的曲奇里选择某一天的一个曲奇
	答案其实也正好是 \prod c_i
	所以我们只需要关心每个人选的那个曲奇了 (神奇的是这个与原问题是等价的)
	设 x_i 表示的是有 x_i 个人在第 i 天得到了它们选择的曲奇
	先不考虑顺序, 钦定是前面 x_i 个人得到了这 x_i 个曲奇
	转移系数是 comb(N - x_i, a_i - x_i) (将剩下还没被选的曲奇随便分给其他人)
	最后再将人排序, 乘上 \frac {N!} {\prod x_i!} (同一天选的与顺序没有关系, 所以要除 x_i!)
	答案其实就是 N! \prod \frac {comb(N - x_i, a_i - x_i)} {x_i!}
	根据这个可以设出状态 f[i][j] 表示前 i 天有 j 个人选了曲奇的方案数
	转移时枚举 x_i 并乘上有关于 x_i 的系数
	状态 O(NK), 转移 O(N), 时间复杂度 O(N^2 K)
*/
#include <bits/stdc++.h>
#define K 25
#define N 1005

using namespace std;

const int mod = 1e9 + 7;

int n, k;
int a[K], f[K][N];
int fac[N], ifac[N];

inline int fpm(int x, int y) {
	int r = 1;
	while(y) {
		if(y & 1) r = 1LL * r * x % mod;
		x = 1LL * x * x % mod, y >>= 1;
	}
	return r;
}
inline int perm(int x, int y) { return 1LL * fac[x] * ifac[x - y] % mod; }
inline int comb(int x, int y) { return 1LL * perm(x, y) * ifac[y] % mod; }

int main() {
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= k; ++i)
		scanf("%d", &a[i]);
	
	fac[0] = 1;
	for(int i = 1; i <= n; ++i) fac[i] = 1LL * i * fac[i - 1] % mod;
	ifac[n] = fpm(fac[n], mod - 2);
	for(int i = n; i; --i) ifac[i - 1] = 1LL * i * ifac[i] % mod;
	
	f[0][0] = 1;
	for(int i = 0; i < k; ++i) {
		for(int j = 0; j <= n; ++j) {
			if(!f[i][j]) continue;
			for(int x = 0; x <= a[i + 1] && j + x <= n; ++x) {
				f[i + 1][j + x] = (f[i + 1][j + x] + 
				1LL * f[i][j] * comb(n - x, a[i + 1] - x) % mod * ifac[x]) % mod;
			}
		}
	}
	
	int ans = 1LL * fac[n] * f[k][n] % mod;
	printf("%d\n", ans);
	return 0;
}