数论

vector<int> primes;
void init(int n) {
    vector<int> vis(n + 1);
    for (int i = 2; i <= n; i++) {
        if (!vis[i])
           primes.push_back(i);

        for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
            vis[i * primes[j]] = 1;
            if (i % primes[j] == 0) break;
        }
    }
}

const int mod = 1e9 + 7;
struct Comb {
    const int N = 5e5;
    vector<int> fac, invfac;

    Comb() {
        init();
    }

    int qpow(int a, int k) {
        int res = 1;
        while (k) {
            if (k & 1) res = res * a % mod;
            a = a * a % mod;
            k >>= 1;
        }
        return res;
    }

    int inv(int x) {
        return qpow(x, mod - 2);
    }

    void init() {
        fac.resize(N + 10), invfac.resize(N + 10);
        fac[0] = 1;
        for (int i = 1; i <= N; i++) {
            fac[i] = fac[i - 1] * i % mod;
        }
        invfac[N] = inv(fac[N]);
        for (int i = N; i > 0; i--) {
            invfac[i - 1] = invfac[i] * i % mod;
        }
    }

    int C(int n, int m) {
        if (n < 0 || n < m) return 0;
        return fac[n] * invfac[m] % mod * invfac[n - m] % mod;
    }
} comb;