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;

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define MP make_pair
#define PB push_back
#define X first
#define Y second

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define ALL(a) a.begin(), a.end()
#define SZ(a) (int)((a).size())
#define FILL(a, value) memset(a, value, sizeof(a))
#define debug(a) cout << #a << " = " << a << endl;

const double PI = acos(-1.0);
const LL INF = 1e9 + 47;
const LL LINF = INF * INF;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

namespace IntModulo
{
	const int mod = 1e9 + 7;

	inline int add(int x, int y, int m = mod)
	{
		if (x + y < m)
			return x + y;
		return x + y - m;
	}

	inline int sub(int x, int y, int m = mod)
	{
		if (x >= y)
			return x - y;
		return x - y + m;
	}

	inline int mult(int x, int y, int m = mod)
	{
		return x * (LL) y % m;
	}

	inline int power(int x, int y, int m = mod)
	{
		int r = 1;
		while(y)
		{
			if (y & 1)
				r = mult(r, x, m);
			x = mult(x, x, m);
			y >>= 1;
		}
		
		return r;
	}
	
	inline int inverse(int x, int m = mod)
	{
		return power(x, m - 2, m);
	}
	
	inline void ADD(int& x, int y, int m = mod)
	{
		x += y;
		if (x >= m) x -= m;
	}
};

using namespace IntModulo;

namespace Combinatorics
{
	using namespace IntModulo;
	
	const int N = 1 << 20;
	int fact[N];
	int inv[N];
	int invFact[N];
	bool inited = false;
	
	inline int C(int n, int k) // binomial C(n, k)
	{
		return n < k ? 0 : mult(fact[n], mult(invFact[k], invFact[n - k]));
	}
	
	inline int H(int n, int k) // number of solution x1 + .. + xn = k
	{
		return C(n + k - 1, k);
	}
	
	void init()
	{
		inited = true;
		inv[1] = 1;
		FOR(i, 2, N)
			inv[i] = mult(mod - mod / i, inv[mod % i]);
		
		invFact[0] = fact[0] = 1;
		FOR(i, 1, N)
		{
			fact[i] = mult(i, fact[i - 1]);
			invFact[i] = mult(invFact[i - 1], inv[i]);
		}
	}	
};

const int N = 1 << 10;
int n, k;
int dp[N];
int dp_new[N];

void go(int x)
{
	FOR(i, 0, n + 1)
	{
		FOR(j, 0, min(n - i, x) + 1)
		{
			int koef = Combinatorics::C(n - j, x - j);
			koef = mult(koef, Combinatorics::C(n - i, j));
			ADD(dp_new[i + j], mult(koef, dp[i]));
		}
	}
	
	FOR(i, 0, n + 1) dp[i] = dp_new[i];
	FILL(dp_new, 0);
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	Combinatorics::init();
	cin >> n >> k;
	dp[0] = 1;
	while(k--)
	{
		int x;
		cin >> x;
		go(x);
	}
	
	cout << dp[n] << endl;
	
	cerr << "Time elapsed: " << clock() / (double)CLOCKS_PER_SEC << endl;
	return 0;
}