Prize Distribution

In a class, there are \(N\) students numbered from \(0\) to \(N-1\). There are \(M\) types of prizes available. The \(i\)-th type of prize has \(a_i\) items (for \(i=0,1,\ldots,M-1\)).

It is guaranteed that the total number of prizes is either \(N\) or \(N+1\), i.e. \[ N \leq \sum_{i=0}^{M-1} a_i \leq N+1, \] meaning that every student can receive exactly one prize and at most one prize is left undistributed.

A distribution scheme is defined as an assignment of a prize type to every student. Two schemes are considered different if at least one student receives a different type of prize.

Your task is to count the number of possible distribution schemes modulo \(10^9+7\>.

Note:

• If \(\sum_{i=0}^{M-1}a_i = N\), then each gift must be used, and for each type \(i\) the number of prizes given is exactly \(a_i\). The number of ways in this case is given by the multinomial coefficient \[ \frac{N!}{a_0!\, a_1!\, \cdots\, a_{M-1}!}. \]
• If \(\sum_{i=0}^{M-1}a_i = N+1\), then exactly one prize remains undistributed. Equivalently, exactly one type \(j\) will supply \(a_j-1\) prizes while for every \(i\neq j\) all \(a_i\) prizes are used. In this case the answer is \[ \sum_{\{j\, :\, a_j>0\}} \frac{N!}{a_0!\cdots (a_j-1)! \cdots a_{M-1}!}. \]

inputFormat

The first line contains an integer \(T\) (\(1 \le T \le 10^5\)), the number of classes (test cases). Each test case is described as follows:

• The first line contains two integers \(N\) and \(M\) (\(1 \le N, M \le 10^5\)).
• The second line contains \(M\) integers \(a_0, a_1, \ldots, a_{M-1}\) satisfying \(0 \leq a_i \leq N+1\) and \(N \leq \sum_{i=0}^{M-1} a_i \leq N+1\).

It is guaranteed that the total input size does not exceed reasonable limits.

outputFormat

For each test case, output a single line containing the number of valid distribution schemes modulo \(10^9+7\).

sample

3
3 2
1 2
3 2
2 2
5 3
2 2 2

3
6
90