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 rep(i, s, t) for (int i = s; i < int(t); ++i)

#define sc	scanf
#define pr	printf
#define ff	first
#define ss	second
#define mp	make_pair
#define pb	push_back
#define eb	emplace_back
#define range(c)	c.begin(), c.end()
#define const_range(c)	c.cbegin(), c.cend()
#define lowbit(x)	((x) & -(x))
#define pop_count	__builin_popcount
#define pop_count64	__builtin_popcountll
#define tail_count	__builtin_ctz
#define tail_count64	__builtin_ctzll
#define lead_count	__builtin_clz
#define lead_count64	__builtin_clzll

#define temp_name template<typename

temp_name T1, typename T2> ostream& operator<< (ostream& os, const pair<T1, T2>& p) { return os << "<" << p.ff << "," << p.ss << ">"; }
#define container_ostream(container)						\
temp_name... T> ostream& operator<< (ostream& os, const container<T...>& c) {	\
	if (c.empty()) return os << "{ }";					\
	auto iter = c.cbegin();							\
	os << "{ " << *iter;							\
	while (++iter != c.cend()) os << ", " << *iter;				\
	return os << " }";							\
}
container_ostream(vector);
container_ostream(set);
container_ostream(map);

void dbg() { cerr << endl;}
temp_name Head, typename... Tail> void dbg(Head h, Tail... t) { cerr << " " << h; dbg(t...); }

#ifdef LOCAL
#define debug(...) cerr << "[ "#__VA_ARGS__" ] :", dbg(__VA_ARGS__)
#else
#define debug(...) 0
#endif

typedef long long i64;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<i64> vl;

temp_name T> T& minn(T& x, const T& y) { return x = min(x, y); }
temp_name T> T& maxx(T& x, const T& y) { return x = max(x, y); }

constexpr const int mod = 1000000007;
constexpr int add(int a, int b) { return a + b < mod ? a + b : a + b - mod; }
constexpr int sub(int a, int b) { return a < b ? mod + a - b : a - b; }
constexpr int mul(int a, int b) { return 1LL * a * b % mod; }
#define more_para(type, func) temp_name... T> constexpr type func(type a, type b, T... c) { return func(func(a, b), c...); }
more_para(int, add);
more_para(int, sub);
more_para(int, mul);
constexpr int square(int a) { return mul(a, a); }
constexpr int fpow(int a, int b) { return b ? mul(b & 1 ? a : 1, square(fpow(a, b >> 1))) : 1; }

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	constexpr const int maxn = 1024;
	vi inv(maxn), fac(maxn), fiv(maxn);
	inv[0] = inv[1] = fac[0] = fac[1] = fiv[0] = fiv[1] = 1;
	rep(i, 2, maxn) {
		inv[i] = mul(inv[mod % i], mod - mod / i);
		fac[i] = mul(fac[i - 1], i);
		fiv[i] = mul(fiv[i - 1], inv[i]);
	}
	auto C = [&] (int n, int k) -> int { return mul(fac[n], fiv[k], fiv[n - k]); };
	int n, k;
	cin >> n >> k;
	vi a(k);
	rep(i, 0, k) cin >> a[i];
	if (accumulate(const_range(a), 0) < n) return cout << "0" << endl, 0;
	vvi f(k);
	rep(i, 0, k) {
		f[i].resize(a[i] + 1);
		rep(j, 0, a[i] + 1) f[i][j] = mul(fiv[j], C(n - j, a[i] - j));
	}
	rep(i, 1, k) {
		vi g(f[0].size() + f[i].size() - 1);
		rep(j0, 0, f[0].size()) rep(j1, 0, f[i].size()) g[j0 + j1] = add(g[j0 + j1], mul(f[0][j0], f[i][j1]));
		f[0] = move(g);
	}
	int ans = mul(f[0][n], fac[n]);
	cout << ans << endl;
}