Dividing Students into Groups

Given a class of \(N\) students, you need to divide them into \(M\) groups for communication. For the \(i\)-th group, the number of students must be strictly greater than a given positive integer \(C_i\). Two arrangements are considered identical if and only if for every group \(i\) the number of students in the \(i\)-th group is the same in both arrangements.

Let \(x_i\) be the number of students in group \(i\). The conditions are:

[ \begin{aligned} x_i &> C_i, \quad \text{for } 1 \le i \le M,\ \sum_{i=1}^{M} x_i &= N. \end{aligned} ]

Define \(y_i = x_i - (C_i+1)\) so that \(y_i \ge 0\). Then the equation becomes:

[ \sum_{i=1}^{M} y_i = N - \sum_{i=1}^{M} (C_i+1) = N - \sum_{i=1}^{M} C_i - M. ]

If we denote \(R = N - \sum_{i=1}^{M} C_i - M\), the number of solutions is given by the stars and bars formula:

[ \binom{R + M - 1}{M - 1} ]

If \(R < 0\), then there is no valid way to partition the class and the answer is 0.

Since the answer can be very large, output the result modulo \(10^9+7\).

inputFormat

The first line contains two integers \(N\) and \(M\) representing the total number of students and the number of groups respectively. The second line contains \(M\) positive integers \(C_1, C_2, \ldots, C_M\) where each \(C_i\) is the given constraint for group \(i\).

outputFormat

Output a single integer representing the number of ways to partition the students modulo \(10^9+7\).

sample

10 3
1 1 1

15