P10112 [GESP202312 Level 8] Prize Distribution

Related multiple-choice and true/false problems: .

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.

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 $T$ lines. Each line contains one integer, which is the number of prize distribution plans for that class modulo $10^{9}+7$.

**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