Modular Arithmetic and Modular Inverses

Modular arithmetic keeps only remainders modulo some m. Whenever a counting problem says "return the answer modulo 10^9 + 7", every intermediate value must be reduced, and the only operation that needs real thought is division, which becomes multiplication by a modular inverse.

Intuition

Remainders are compatible with addition, subtraction and multiplication:

• (a + b) mod m = ((a mod m) + (b mod m)) mod m
• (a - b) mod m = ((a mod m) - (b mod m)) mod m
• (a * b) mod m = ((a mod m) * (b mod m)) mod m

So you may reduce after every step and the final remainder is unchanged. Division is different: 6 / 2 = 3, but you cannot divide remainders. Instead multiply by the inverse: b^-1 is the number with b * b^-1 = 1 (mod m). It exists exactly when gcd(b, m) = 1.

• Prime modulus (Fermat's little theorem): for prime p and b not divisible by p, b^(p-1) = 1 (mod p), so b^(p-2) is the inverse. One fast exponentiation.
• Any modulus: the extended Euclidean algorithm finds x with b*x + m*y = 1; that x is the inverse.
• Euler's theorem generalizes Fermat: if gcd(a, m) = 1, then a^phi(m) = 1 (mod m), which lets you reduce a huge exponent modulo phi(m) (modulo p - 1 for a prime).

Why 10^9 + 7 specifically? It is prime (so every non-multiple has an inverse), the sum of two residues fits in a signed 32-bit integer, and the product of two residues fits in a signed 64-bit integer.

When to use it in interviews / OAs

• "The answer may be large; return it modulo 10^9 + 7" (counting, DP, combinatorics).
• Formulas with division: n! / (k! (n-k)!), averages, probabilities and expected values reported as P * Q^-1 mod p.
• Huge powers: exponents up to 10^18 or given as strings.
• Lazily applied affine operations (add, multiply) where an earlier multiplication must be undone: needs inverses.

Language semantics

In C++ and Java, % keeps the sign of the dividend: -7 % 3 == -1. In Python, % follows the divisor: -7 % 3 == 2. After any subtraction in C++/Java, normalize with ((a % m) + m) % m. Also in C++/Java, a * b % m with int operands overflows before the %; write 1LL * a * b % m (C++) or use long (Java). Python's integers never overflow, but reducing early still keeps them small and fast.

Template

MOD = 10**9 + 7


def ext_gcd(a: int, b: int) -> tuple[int, int, int]:
    # returns (g, x, y) with a*x + b*y == g == gcd(a, b)
    if b == 0:
        return a, 1, 0
    g, x, y = ext_gcd(b, a % b)
    return g, y, x - a // b * y


def inv_fermat(a: int, p: int = MOD) -> int:
    # p must be prime and a not a multiple of p
    return pow(a, p - 2, p)


def inv_general(a: int, m: int) -> int:
    # works for any modulus, as long as gcd(a, m) == 1
    g, x, _ = ext_gcd(a % m, m)
    if g != 1:
        raise ValueError("inverse does not exist")
    return x % m

Since Python 3.8, pow(a, -1, m) does the same job as inv_general.

Many inverses at once

Combinatorics needs 1 / k! for every k up to n. Two O(n) tricks:

def inverses_up_to(n: int, p: int = MOD) -> list[int]:
    # inv[i] for 1 <= i <= n (p prime, n < p): write p = (p // i) * i + p % i
    inv = [0, 1] + [0] * (n - 1)
    for i in range(2, n + 1):
        inv[i] = (p - p // i) * inv[p % i] % p
    return inv


def factorial_tables(n: int, p: int = MOD) -> tuple[list[int], list[int]]:
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i % p
    inv_fact = [1] * (n + 1)
    inv_fact[n] = pow(fact[n], p - 2, p)  # one exponentiation for the largest factorial...
    for i in range(n, 0, -1):
        inv_fact[i - 1] = inv_fact[i] * i % p  # ...then 1/(i-1)! = i * (1/i!)
    return fact, inv_fact

The first comes from p = q*i + r, so q*i + r = 0 (mod p), hence 1/i = -q / r = -q * inv[r], with r < i already known. With both factorial tables, C(n, k) = fact[n] * inv_fact[k] * inv_fact[n-k] mod p in O(1) per query.

Fractions and huge exponents

Many modern problems report a probability or expectation P / Q as P * Q^-1 mod p. For example the expected value of a fair die, 7/2, is reported as 500000007, because 2 * 500000007 = 7 (mod 10^9 + 7).

def fraction_mod(num: int, den: int, p: int = MOD) -> int:
    # the residue r with r * den == num (mod p); den must not be a multiple of p
    return num % p * pow(den, p - 2, p) % p


def pow_huge_exponent(a: int, e_digits: str, p: int = MOD) -> int:
    # a^e mod p for a decimal exponent string; needs p prime and a % p != 0
    e = 0
    for ch in e_digits:
        e = (e * 10 + int(ch)) % (p - 1)  # Fermat: exponents only matter modulo p - 1
    return pow(a, e, p)

Complexity

Addition and multiplication are O(1). One inverse costs O(log m) (fast (binary) exponentiation or extended Euclid). The linear inverse table and the factorial tables cost O(n) time and memory. Reducing a decimal exponent string costs O(length).

Common pitfalls

• Negative remainders in C++/Java after subtraction: add m before the final %.
• Overflow before the modulo: multiply in 64-bit (1LL * a * b % m); a product of three residues needs an intermediate %.
• Inverse that does not exist: Fermat requires a prime modulus and a base not divisible by it. With a composite modulus (like 10^9) many numbers have no inverse; restructure the formula or use a different approach (Pascal's triangle for binomials, for example).
• Comparing reduced values: once values are reduced, you cannot take max or compare them meaningfully. Do comparisons on true values (or on logarithms) and reduce only what you output.
• Reducing the exponent with the wrong modulus: exponents reduce modulo p - 1 (or phi(m)), not modulo p, and only when the base is coprime to the modulus.
• Forgetting to reduce inputs: values up to 10^18 should be reduced before multiplying in fixed-width languages.

Interview variations

• Any counting DP "modulo 10^9 + 7": reduce after each addition.
• nCr modulo a prime for many queries: factorial and inverse factorial tables.
• Expected value or probability as a modular fraction: P * Q^-1 mod p.
• Sum of subsequence widths, count good numbers: powers of 2 or other bases modulo p.
• Sequence with lazy "add to all" and "multiply all": store a global affine map and undo it with a modular inverse.
• Super pow: huge exponents, reduced by Euler's theorem or processed digit by digit.