Modular Arithmetic

O(log e) per power/inverse

Fast exponentiation and modular inverse under a prime modulus, the base layer of counting problems that ask for the answer mod 1e9+7 or 998244353. Division becomes multiplication by the inverse (Fermat's little theorem, prime modulus only).

// use it on

CSES: Exponentiation ↗

Raw a^b mod 1e9+7 with huge exponents. Binary exponentiation is the entire problem.

// the code

const long long MOD = 998244353;  // or 1e9+7

long long power(long long b, long long e, long long mod = MOD) {
    long long r = 1;
    for (b %= mod; e > 0; e >>= 1, b = b * b % mod)
        if (e & 1) r = r * b % mod;
    return r;
}

long long inv(long long a) {  // MOD must be prime
    return power(a, MOD - 2);
}

// usage: (x * inv(y)) % MOD  computes  x / y  (mod MOD)

// more mathematics

Extended GCD & CRT Sieve (Smallest Prime Factor)Binomial Coefficients (nCr)Matrix Exponentiation NTT (Convolution)