思路与算法

不同晚上的选择必须不同，而每晚只选择一个大小为 $m$ 的无序子集，所以可持续晚数恰为 $\binom nm$。$n$ 可大于固定素数10007，不能直接对 $n!$ 求逆。

Lucas定理把大组合数拆成素数 $P$ 进制的数位乘积：

先预处理 $0,\ldots,P-1$ 的阶乘和逆阶乘。每一位都小于 $P$，对应阶乘非零，若 $m_j>n_j$ 就返回0，否则乘上该位的小组合数。然后两参数整除 $P$，直到都为0。本题取 $P=10007$，预处理一次后复用到全部 $t$ 组查询。

正确性说明

每个 $m$ 人子集对应一种且仅一种晚上的选择，故答案为组合数。对素数 $P$，二项式系数满足Lucas数位分解；合法数位的小组合数通过可逆阶乘精确计算，非法位表示对应因子为0。逐位相乘就是目标余数，终止时无剩余数位。预处理只到 $P-1$，没有给不可逆的 $P!$ 或大阶乘求逆，因此方法对 $n\ge P$ 仍正确。

复杂度

阶乘数组初始化和双向预处理 $O(P)$，一次模逆快速幂 $O(\log P)$；单次Lucas为 $O(\log_P(n+1))$ 位。含全部查询总时间 $O(P+\log P+t+\sum_q\log_P(n_q+1))$，额外空间 $O(P)$，$P=10007$。

易错点

1. 输入是 $n,m$，不是某些组合模板中的 $n+m,m$；模数固定10007。
2. 即使整体 $m\le n$，也可能有某一位 $m_j>n_j$，此时答案为0。
3. 最低位为0时 $\binom00=1$，不能提前把整项设为0。
4. $m=n$ 结果为1；$n=P,m=1$ 为0。覆盖跨模数、最大 $n,m$ 与最多200组输入。
5. 独立答案用p进赋值和去p阶乘单位部分，未复用Lucas数位乘积，并与500个小范围精确组合数对照。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int P = 10007;
ll power(ll a, ll e) {
    ll result = 1;
    while (e) {
        if (e & 1)
            result = result * a % P;
        a = a * a % P;
        e >>= 1;
    }
    return result;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<ll> fact(P), inv(P);
    fact[0] = 1;
    for (int i = 1; i < P; i++)
        fact[i] = fact[i - 1] * i % P;
    inv[P - 1] = power(fact[P - 1], P - 2);
    for (int i = P - 1; i; i--)
        inv[i - 1] = inv[i] * i % P;
    auto lucas = [&](ll n, ll m) -> ll {
        ll answer = 1;
        while (n || m) {
            int a = n % P, b = m % P;
            if (b > a)
                return 0;
            answer = answer * fact[a] % P * inv[b] % P * inv[a - b] % P;
            n /= P;
            m /= P;
        }
        return answer;
    };
    int tests;
    cin >> tests;
    while (tests--) {
        ll n, m;
        cin >> n >> m;
        cout << lucas(n, m) << '\n';
    }
}