Modular Arithmetic: Fast Exponentiation and Inverse

a^8 = ((a^2)^2)^2  — 3 multiplications instead of 7
a^13 = a^8 * a^4 * a^1  — binary 1101

#include <stdio.h>

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

// Modular inverse via Fermat (mod must be prime)
long long mod_inv(long long a, long long mod) {
    return power(a, mod - 2, mod);
}

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

const long long MOD = 1e9 + 7;

long long power(long long base, long long exp, long long mod = MOD) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

// Precompute factorials and inverse factorials for nCr
struct Combinatorics {
    int n;
    vector<long long> fact, inv_fact;
    Combinatorics(int n) : n(n), fact(n+1), inv_fact(n+1) {
        fact[0] = 1;
        for (int i = 1; i <= n; i++) fact[i] = fact[i-1] * i % MOD;
        inv_fact[n] = power(fact[n], MOD - 2);
        for (int i = n-1; i >= 0; i--) inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
    }
    long long C(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD;
    }
};

public class ModArith {
    static final long MOD = 1_000_000_007L;

    public static long power(long base, long exp, long mod) {
        long result = 1;
        base %= mod;
        while (exp > 0) {
            if ((exp & 1) == 1) result = result * base % mod;
            base = base * base % mod;
            exp >>= 1;
        }
        return result;
    }

    public static long modInv(long a, long mod) {
        return power(a, mod - 2, mod); // mod must be prime
    }

    public static long nCr(int n, int k, long[] fact, long[] invFact) {
        if (k < 0 || k > n) return 0;
        return fact[n] * invFact[k] % MOD * invFact[n - k] % MOD;
    }
}

const MOD = BigInt(1e9 + 7);

function power(base, exp, mod = MOD) {
    base = BigInt(base); exp = BigInt(exp); mod = BigInt(mod);
    let result = 1n;
    base %= mod;
    while (exp > 0n) {
        if (exp & 1n) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1n;
    }
    return result;
}

// Precompute factorials
function buildFactorials(n) {
    const fact = new Array(n + 1).fill(0n);
    const invFact = new Array(n + 1).fill(0n);
    fact[0] = 1n;
    for (let i = 1; i <= n; i++) fact[i] = fact[i - 1] * BigInt(i) % MOD;
    invFact[n] = power(fact[n], MOD - 2n);
    for (let i = n - 1; i >= 0; i--) invFact[i] = invFact[i + 1] * BigInt(i + 1) % MOD;
    return { fact, invFact };
}

MOD = 10**9 + 7

def power(base, exp, mod=MOD):
    result = 1
    base %= mod
    while exp > 0:
        if exp & 1:
            result = result * base % mod
        base = base * base % mod
        exp >>= 1
    return result

# Python built-in: pow(base, exp, mod)

# Precompute factorials for O(1) nCr
def precompute(n, mod=MOD):
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i-1] * i % mod
    inv_fact = [1] * (n + 1)
    inv_fact[n] = pow(fact[n], mod - 2, mod)
    for i in range(n - 1, -1, -1):
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % mod
    def nCr(n, k):
        if k < 0 or k > n: return 0
        return fact[n] * inv_fact[k] % mod * inv_fact[n-k] % mod
    return nCr

nCr = precompute(10**6)
print(nCr(10, 3))  # 120