题目背景

2023 年 12 月 GESP C++ 八级编程第 1 题

题目描述

有 $T$ 个班级需要分配奖品。对每个班级，有 $N$ 名同学，学号从 $0$ 到 $N-1$，以及 $M$ 种奖品，第 $i$ 种奖品共有 $a_i$ 个。保证奖品总数为 $N$ 或 $N+1$。

每位同学必须恰好获得一个奖品。只要存在一名同学获得的奖品种类不同，就认为是不同方案。请对每个班级求分配方案数，并对 $10^9+7$ 取模。

输入格式

第一行输入整数 $T$。 接下来 $T$ 行，每行先输入两个正整数 $N,M$，再输入 $M$ 个正整数 $a_0,a_1,ldots,a_{M-1}$。

输出格式

输出 $T$ 行，每行一个整数，表示对应班级的方案数对 $10^9+7$ 取模后的结果。

3
3 2 1 2
3 2 1 3
5 3 3 1 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

数据范围与提示

• 对于 $30\%$ 的测试点，保证 $N\le 10$。
• 另有 $30\%$ 的测试点，保证 $M=2$。
• 对于全部测试点，保证 $1\le T\le 1000$，$1\le N\le 1000$，$1\le M\le 1001$，$a_i\ge1$，且 $N\le\sum a_i\le N+1$。

来源

GESP 2023 年 12 月 C++ 八级 T1