Counting Distinct Suffix Arrays

Little P once attended the NOIP2044 contest and encountered a problem: given a string s = s₁s₂...s_n of length n composed of at most m different characters, where the i-th type of character appears at most c_i times, one is asked to compute its suffix array. A suffix array of a string s is defined as a permutation p₁, p₂, ..., p_n such that if we define suf(i)=s[i...n] for 1 ≤ i ≤ n then

$$\mathrm{suf}(p_1) < \mathrm{suf}(p_2) < \dots < \mathrm{suf}(p_n). $$

When comparing two strings s and t, if i is the first position where they differ, then the string whose i-th character is smaller is considered smaller; if no such i exists the shorter string is considered smaller. Furthermore, for the ordering of characters we assume that the 1^st character is the smallest, the 2^nd is the next smallest, and so on.

Inspired by this, Little P devised a new challenge for you:

Under the same restrictions, count how many different suffix arrays can appear among all strings of length n consisting of exactly these m characters, where for each 1 ≤ i ≤ m the i-th character appears no more than c_i times. As the answer can be huge, output it modulo $$10^9+7$$.

Input Format: The first line contains two integers n and m. The second line contains m integers, where the i-th integer is c_i.

Note: The suffix array for a string s = s₁s₂...s_n is defined as the permutation p₁, p₂, ..., p_n such that the list of suffixes suf(p₁), suf(p₂), …, suf(pₙ) is sorted according to the order defined above.

inputFormat

The first line contains two integers n and m (the length of the string and the number of available characters). The second line contains m integers: c₁, c₂, ..., cₘ, where each c_i indicates the maximum number of times the i-th character may appear.

outputFormat

Output a single integer, which is the number of different suffix arrays produced by all valid strings, taken modulo $$10^9+7$$.

sample

2 2
1 1

2