你好！我是你的OI教练。这是一道典型的组合数学题目，结合了多重集排列和模逆元的知识。

这道题虽然是八级题目，但只要透过现象看到本质，它的核心公式非常简洁。让我们一起来拆解它。

1. 题目分析与思路推导

核心问题

我们需要把 $S$ 个奖品（$S = \sum a_i$）分配给 $N$ 个同学。题目保证 $S$ 要么等于 $N$，要么等于 $N+1$。

情况一：奖品数量恰好等于人数 ($S = N$)

这是一个经典的多重集全排列问题。 如果我们有 $N$ 个位置和 $N$ 个物品，其中第 $i$ 种物品有 $a_i$ 个，那么排列的总方案数为：

$$\text{Ans} = \frac{N!}{a_0! \times a_1! \times \dots \times a_{M-1}!} $$

解释：$N!$ 是假设所有物品都不同时的排列数，分母中的 $a_i!$ 是为了消除同种物品内部顺序造成的重复计算。

情况二：奖品数量多出一个 ($S = N+1$)

这表示有 $N$ 个同学分到了奖品，剩下了 $1$ 个奖品。 我们可以换个角度思考：假设有一个虚拟的“第 $N+1$ 位同学”（或者叫“垃圾桶”）。 我们把 $N+1$ 个奖品分给 $N$ 个真实的同学和 $1$ 个虚拟的同学。每个人（包括虚拟的那个）都恰好拿一个奖品。 这样问题就转化为了：将 $N+1$ 个物品进行全排列。 公式为：

$$\text{Ans} = \frac{(N+1)!}{a_0! \times a_1! \times \dots \times a_{M-1}!} $$

统一公式

观察上面两种情况，我们发现分子总是奖品总数 $S$ 的阶乘，分母总是各类奖品数量阶乘的乘积。

$$\text{Ans} = \frac{S!}{\prod_{i=0}^{M-1} a_i!}$$

其中 $S = \sum a_i$。

2. 预备知识点

1. 模运算性质：$(a \times b) \pmod P = ((a \pmod P) \times (b \pmod P)) \pmod P$。
2. 除法取模（逆元）：
   • 在模 $10^9+7$（质数）下，除以一个数等于乘以这个数的逆元。
   • 根据费马小定理，$x$ 的逆元 $x^{-1} \equiv x^{MOD-2} \pmod{MOD}$。
   • 公式变成：$\text{Ans} = S! \times (a_0!)^{-1} \times (a_1!)^{-1} \dots \pmod{MOD}$。
3. 预处理：
   • 因为 $N$ 只有 1000，我们可以预处理出所有数字的阶乘 fact[] 和阶乘的逆元 invFact[]，这样每次查询的复杂度仅为 $O(M)$。

3. C++ 标准代码 (NOIP C++14)

/**
 * 题目：P10112 [GESP202312 八级] 奖品分配
 * 考点：组合数学、多重集排列、乘法逆元
 * 时间复杂度：预处理 O(N)，单次查询 O(M)
 */

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 2005; // 奖品总数最多为 N+1，N<=1000，开2005足够

long long fact[MAXN];    // 存储阶乘
long long invFact[MAXN]; // 存储阶乘的逆元

// 快速幂计算 x^y % p
long long qpow(long long x, long long y) {
    long long res = 1;
    while (y > 0) {
        if (y & 1) res = res * x % MOD;
        x = x * x % MOD;
        y >>= 1;
    }
    return res;
}

// 初始化阶乘和逆元
void init() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        fact[i] = fact[i - 1] * i % MOD;
    }

    // 计算最大值的逆元 (费马小定理)
    invFact[MAXN - 1] = qpow(fact[MAXN - 1], MOD - 2);

    // 递推计算前面所有数的逆元
    // (i!)^{-1} = ((i+1)!)^{-1} * (i+1)
    for (int i = MAXN - 2; i >= 0; i--) {
        invFact[i] = invFact[i + 1] * (i + 1) % MOD;
    }
}

void solve() {
    int N, M;
    cin >> N >> M;
    
    vector<int> a(M);
    long long S = 0; // 奖品总数
    
    for (int i = 0; i < M; i++) {
        cin >> a[i];
        S += a[i];
    }

    // 根据公式：Ans = S! / (a0! * a1! * ... * am!)
    // 在模意义下变为：Ans = S! * inv(a0!) * inv(a1!) ...
    
    long long ans = fact[S]; // 分子 S!
    
    for (int i = 0; i < M; i++) {
        // 乘以分母的逆元
        ans = ans * invFact[a[i]] % MOD;
    }

    cout << ans << endl;
}

int main() {
    // IO优化
    ios::sync_with_stdio(false);
    cin.tie(0);

    init(); // 预处理阶乘和逆元

    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

4. 代码关键点注释

1. 数据范围：题目中 $N \le 1000$，但奖品总数可能是 $N+1$，所以数组大小至少要开到 1002。为了保险起见，代码中开了 2005。
2. 逆元递推优化：
   • 通常求逆元是用快速幂，单次 $O(\log N)$。
   • 这里利用 invFact[i] = invFact[i+1] * (i+1) 的性质进行线性递推，可以在 $O(N)$ 时间内求出所有阶乘的逆元，比每次都算一遍快速幂要快。
3. long long：中间计算过程涉及乘法，结果会超过 int 范围，必须全程使用 long long。
4. $S=N+1$ 的理解：如果不理解虚拟同学的概念，很容易卡在这里。记住：把多出来的那个奖品看作被“虚空”拿走了，本质上就是对 $N+1$ 个物品全排列。

5. 数据生成器 (Data Generator)

这是用于生成测试数据（1.in ~ 10.in）的代码，覆盖了题目要求的各种边界情况。

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <numeric>
#include <cstdlib>
#include <ctime>
#include <algorithm>

using namespace std;

// 随机整数生成 [min, max]
int randInt(int min, int max) {
    return rand() % (max - min + 1) + min;
}

// 解决单个Case并返回结果，用于生成 .out 文件
// 这里直接复制上面的逻辑
const int MOD = 1e9 + 7;
const int MAXN_GEN = 2005;
long long fact_gen[MAXN_GEN], invFact_gen[MAXN_GEN];

long long qpow_gen(long long x, long long y) {
    long long res = 1;
    while (y > 0) {
        if (y & 1) res = res * x % MOD;
        x = x * x % MOD;
        y >>= 1;
    }
    return res;
}

void init_gen() {
    fact_gen[0] = 1;
    for (int i = 1; i < MAXN_GEN; i++) fact_gen[i] = fact_gen[i - 1] * i % MOD;
    invFact_gen[MAXN_GEN - 1] = qpow_gen(fact_gen[MAXN_GEN - 1], MOD - 2);
    for (int i = MAXN_GEN - 2; i >= 0; i--) invFact_gen[i] = invFact_gen[i + 1] * (i + 1) % MOD;
}

long long solve_case(int N, int M, vector<int>& a) {
    long long S = 0;
    for(int x : a) S += x;
    long long ans = fact_gen[S];
    for(int x : a) ans = ans * invFact_gen[x] % MOD;
    return ans;
}

void makeData(int id) {
    string inName = to_string(id) + ".in";
    string outName = to_string(id) + ".out";
    ofstream fin(inName);
    ofstream fout(outName);

    int T;
    
    // 根据测试点编号设置难度
    if (id <= 3) {
        // 30% 数据 N <= 10
        T = 10;
    } else if (id <= 6) {
        // 另外 30% 数据 M = 2
        T = 50;
    } else {
        // 100% 数据 N <= 1000
        T = 100; // T <= 1000, 取100个比较适中
    }
    
    fin << T << endl;

    for (int t = 0; t < T; t++) {
        int N, M;
        
        if (id <= 3) {
            N = randInt(1, 10);
            M = randInt(1, N + 1);
        } else if (id <= 6) {
            N = randInt(10, 1000);
            M = 2;
        } else {
            N = randInt(100, 1000);
            M = randInt(1, 100); // M不必很大，关键是和为N或N+1
        }
        
        // 决定总和是 N 还是 N+1
        int S = (randInt(0, 1) == 0) ? N : N + 1;
        
        // 随机分配 a_i
        // 算法：把 S 个球放入 M 个盒子，且允许空盒（题目说a_i是正整数，所以不允许空盒）
        // 题目说 a_i 是正整数，所以每个盒子至少放1个。
        // 我们先给每个盒子放1个，剩下 S - M 个随机分。
        // 如果 S < M，这种情况在正整数限制下是不合法的，需要重置 M
        if (M > S) M = S; 
        
        vector<int> a(M, 1);
        int remain = S - M;
        for (int k = 0; k < remain; k++) {
            a[randInt(0, M - 1)]++;
        }

        fin << N << " " << M;
        for (int x : a) fin << " " << x;
        fin << endl;

        fout << solve_case(N, M, a) << endl;
    }

    fin.close();
    fout.close();
    cout << "Generated Case " << id << endl;
}

int main() {
    srand(time(0));
    init_gen();
    for (int i = 1; i <= 10; i++) {
        makeData(i);
    }
    return 0;
}