Background

Related multiple-choice and true/false problems: https://ti.luogu.com.cn/problemset/1140.

Problem Description

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

By coincidence, the number of prizes is neither too many nor too few: each student can receive exactly one prize, and the number of prizes left in the end is at most $1$ (i.e., $N\le a_0+a_1+\cdots+a_{M-1}\le N+1$).

Now, please find the number of possible prize distribution plans for each class. A plan means assigning each student a prize type.

If at least one student receives a different type of prize, it is considered a different plan. 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 them one by one.

Input Format

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

In the next $T$ lines, each line contains several positive integers separated by single spaces. First come two positive integers $N,M$, followed by $M$ positive integers $a_0,a_1...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 line contains one integer, which is the number of prize distribution plans for that class modulo $10^{9}+7$.

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

3
4
20

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

1
1
125970
895031741
307187590

Hint

Sample Explanation 1

For the $1$-st class, students with IDs $0,1,2$ can receive prizes $0,1,1$ in order, or $1,0,1$ in order, or $1,1,0$ in order, so there are $3$ plans in total.

For the $2$-nd class, students with IDs $0,1,2$ can receive prizes $0,1,1$ in order, or $1,0,1$ in order, or $1,1,0$ in order, or $1,1,1$ in order, so there are $4$ plans in total.

For the $3$-rd class, you can assign the prize with ID $0$ to any one of the $5$ students, giving $5$ choices; then assign the prize with ID $2$ to any one of the remaining $4$ students, giving $4$ choices; finally, the remaining $3$ students naturally receive prize $1$. Therefore, the number of plans is $5 \times 4 = 20$.

Constraints

For $30\%$ of the test points, $N \le 10$.

For another $30\%$ of the test points, $M=2$.

For all test points, $N \le 1000$; $T \le 1000$; $M \le 1001$.

Translated by ChatGPT 5