费马定理以及逆元预处理

#include <bits/stdc++.h>
using namespace std;

static const int MOD = 1000000007;

// 预先全局存放阶乘与逆阶乘的数组
static const int MAXN = 100000;  // 根据题意，n最多10^5
long long fact[MAXN+1], invFact[MAXN+1];

// 快速幂，用于求 x^y % MOD
long long fastPow(long long base, long long exp) {
    long long result = 1 % MOD;
    base = base % MOD;
    while (exp > 0) {
        if (exp & 1) result = (result * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return result;
}

// 预计算 factorial 和 invFactorial
// fact[i] = i! % MOD
// invFact[i] = (i!)^(-1) % MOD
void precomputeFactorials(int n) {
    fact[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = fact[i-1] * i % MOD;
    }
    invFact[n] = fastPow(fact[n], MOD-2);  // 使用费马小定理求逆
    for (int i = n-1; i >= 0; i--) {
        invFact[i] = invFact[i+1] * (i+1) % MOD;
    }
}

// 计算组合数 C(n, r) = n! / (r! * (n-r)!)
long long binomial(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fact[n] * invFact[r] % MOD * invFact[n-r] % MOD;
}