Problem Description

There are $N$ students in a class, with student IDs ranging from $0$ to $N-1$. There are $M$ types of prizes to be distributed among these students, where the $i$-th type of prize has a total of $a_i$ units ($i=0,1,\cdots,M-1$).

It happens that the number of prizes is just right, so that each student can receive exactly one prize, and there will be no more than one prize left over (i.e., $N \le a_0 + a_1 + \cdots + a_{M-1} \le N+1$).

Now, you are asked to calculate the number of ways to distribute the prizes, where a scheme refers to assigning one type of prize to each student.

A scheme is considered different if at least one student receives a different type of prize. For convenience, you only need to output the result modulo $10^9 + 7$.

There are $T$ classes facing the prize distribution problem, and you need to solve it for each of them in order.

Input Format

The first line contains an integer $T$, representing the number of classes.

The next $T$ lines each contain several positive integers separated by single spaces. The first two integers are $N$ and $M$, followed by $M$ positive integers $a_0, a_1, \ldots, a_{M-1}$. It is guaranteed that $N \le a_0 + a_1 + \cdots + a_{M-1} \le N+1$.

Output Format

Output $T$ lines, each containing an integer representing the number of ways to distribute the prizes for that class modulo $10^9 + 7$.

Sample Input and Output

Input Sample #1

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

Output Sample #1

3
4
20

Input Sample #2

5
100 1 100
100 1 101
20 2 12 8
123 4 80 20 21 3
999 5 101 234 499 66 99

Output Sample #2

1
1
125970
895031741
307187590

Notes

Sample Explanation 1

For the first class, the students with IDs $0, 1, 2$ can receive prizes $0, 1, 1$ respectively, or $1, 0, 1$, or $1, 1, 0$, resulting in 3 different schemes.

For the second class, the students with IDs $0, 1, 2$ can receive prizes $0, 1, 1$, or $1, 0, 1$, or $1, 1, 0$, or $1, 1, 1$, resulting in 4 different schemes.

For the third class, the prize with ID $0$ can be assigned to any of the 5 students, resulting in 5 ways; then the prize with ID $2$ can be assigned to any of the remaining 4 students, resulting in 4 ways; finally, the remaining 3 students naturally receive the prize with ID $1$. Thus, the number of schemes is $5 \times 4 = 20$.

Data Range

For 30% of the test cases, it is guaranteed that $N \le 10$.

For another 30% of the test cases, it is guaranteed that $M = 2$.

For all test cases, it is guaranteed that $N \le 1000$; $T \le 1000$; $M \le 1001$.

见题面 Input 部分

见题面 Output 部分