Little P arrived at the NOIP2044 competition, where he found the second problem to be: Given a string of length $n$ composed of at most $m$ distinct characters, where the $i$-th character appears at most $c_i$ times, what is the suffix array of this string?

The clever Little P thought of a new problem and would like your help to solve it: Under the given constraints, how many different answers are there? That is, among all strings of length $n$ composed of $m$ types of characters where the $i$-th character appears at most $c_i$ times, how many distinct suffix arrays are there in total?

Since the answer can be very large, output the answer modulo $10^9+7$.

For a string $s=s_1s_2...s_n$, let $\mathrm{suf}(i)$ denote the suffix starting at position $i$ to the end. The suffix array is a permutation $p_1,p_2,...,p_n$ of $1$ to $n$ such that $\mathrm{suf}(p_1)< \mathrm{suf}(p_2)< \dots < \mathrm{suf}(p_n)$. For two strings $s$ and $t$, let $i$ be the first position where $s_i \neq t_i$; then the string with the smaller character at $s_i$ and $t_i$ is smaller. If no such $i$ exists, the shorter string is smaller.

Regarding the order of characters, we define the 1st character as the smallest, the 2nd character as the second smallest, and so on.

Input

The first line contains two positive integers $n, m$, representing the length of the string $n$ and the number of character types $m$.

The next line contains $m$ non-negative integers $c_1, c_2, ..., c_m$, representing the maximum number of occurrences for each character type. It is guaranteed that $0 \leq c_1, c_2, ..., c_m \leq n$ and $c_1+c_2+...+c_m \geq n$.

Output

Output a single line containing a positive integer representing the answer.

Examples

Input 1

3 2
2 2

Output 1

5

Note

Let $a$ be the first character and $b$ be the second character. There are six possible strings: $aab, aba, abb, baa, bab, bba$. Their suffix arrays are: \begin{equation} (1,2,3),(3,1,2),(1,3,2),(3,2,1),(2,3,1),(3,2,1). \end{equation} Thus, there are $5$ distinct results.

Input 2

10 5
2 3 4 3 2

Output 2

1003811

Input 3

See the provided files.

Subtasks