预处理

using ll = long long;
const int N = 1e6 + 5;
const int MOD = 1e9 + 7;

// 阶乘与组合数预处理 
ll fact[N], inv[N];

ll qpow(ll a, ll b) {
    ll res = 1;
    for (a %= MOD; b > 0; b >>= 1, a = a * a % MOD) {
        if (b & 1) res = res * a % MOD;
    }
    return res;
}

void init_fac(int n) {
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i % MOD;
    inv[n] = qpow(fact[n], MOD - 2);
    for (int i = n - 1; i >= 0; --i) inv[i] = inv[i + 1] * (i + 1) % MOD;
}

inline ll C(int n, int k) {
    if (n < 0 || k < 0 || k > n) return 0;
    return fact[n] * inv[k] % MOD * inv[n - k] % MOD;
}