Modular Arithmetic Explained: Why Answers Use Mod 10^9 + 7

"Return the answer modulo 10^9 + 7" appears at the bottom of many counting problems, and it is easy to treat it as boilerplate: add % MOD at the end and move on. That is how correct solutions time out or overflow. The instruction exists because the true answer is astronomically large, and the only way to keep the numbers small is to reduce during the computation, not after. Knowing which operations allow that, and which one does not, is the whole topic.

The problem it solves

Counting problems grow fast. The number of paths through a grid, the number of ways to climb stairs or to arrange items quickly passes any 64-bit integer. In languages with fixed-width integers the computation silently overflows. In Python it does not overflow, but every addition and multiplication on a thousand-digit number costs far more than one on a machine word.

Modular arithmetic keeps only the remainder after division by m. The results live on a clock with m positions, from 0 to m - 1, and the key fact is that reducing early does not change where you land.

The intuition

Think of x % m as a position on the clock face. Adding a multiple of m walks whole laps and lands in the same place. So for addition, subtraction and multiplication, you may reduce any operand at any time:

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

Division is the exception. (a / b) % m is not (a % m) / (b % m): the reduced values may not even divide. Instead you multiply by the modular inverse of b, the number x with b * x % m == 1. It exists exactly when b and m share no factor, which the Euclidean algorithm decides. When m is prime, Fermat's little theorem gives it directly: b^(m-2) % m, computed with fast exponentiation.

That explains the choice of 10^9 + 7. It is prime, so every value that is not a multiple of it has an inverse. It is below 2^31, so a residue fits in a signed 32-bit integer and so does the sum of two residues. And the product of two residues, about 10^18, fits in a signed 64-bit integer, whose limit is about 9.2 × 10^18. It is large enough that a wrong answer is unlikely to match the right one by accident, and small enough that no step overflows. 998244353 is the other common choice, for similar reasons plus its use in number-theoretic transforms.

Negative numbers differ by language. Python's % takes the sign of the divisor, so -3 % 12 is 9, a real position on the face. C, C++, Java and Go truncate, so -3 % 12 is -3 there, and the portable fix is ((a % m) + m) % m.

Watch it run

The animation is a twelve-position clock. Step past 11 and you are back at 0, and that wrap is the whole of modular arithmetic. Forty-five minutes past the hour is three full laps and nine more: the hand stops on 9. Now add 31. The hand walks on, sails past 11 and keeps going, 76 in total. It lands on 4; six laps of the face were never worth counting. Reduce first instead: 45 becomes 9 and 31 becomes 7, and nine plus seven is 16, one lap plus 4. Same position. That is the rule worth keeping: reduce whenever you like, and the answer never moves. Multiplication behaves the same way: 9 × 7 = 63, five laps and 3. Subtraction walks backwards; three places below 0 is 9, because Python's % always answers with a position on the face. The closing frame names the users: hashes, wrap-around buffers and huge powers, all with numbers that never grow.

The code

The lesson's clock, then the reason to reduce early even in Python: the 10,000th Fibonacci number has almost 7,000 bits, while the reduced version always stays below 2^30:

m = 12
print((45 + 31) % m, ((45 % m) + (31 % m)) % m)    # 4 4
print((9 * 7) % m, -3 % m)                          # 3 9

MOD = 10**9 + 7

def fib(n, mod=None):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b if mod is None else (a + b) % mod
    return a

big = fib(10_000)
print(big.bit_length(), fib(10_000, MOD).bit_length())   # 6942 29
print(big % MOD == fib(10_000, MOD))                     # True

The size argument for 10^9 + 7, checked against the 32-bit and 64-bit signed limits, and the negative remainder you get from truncating languages, reproduced with math.fmod:

import math

INT32, INT64 = 2**31 - 1, 2**63 - 1
top = MOD - 1                                  # the largest residue
print(top + top <= INT32, top * top <= INT64)  # True True
print(all(MOD % d for d in range(2, math.isqrt(MOD) + 1)))   # True  (prime)

print(math.fmod(-3, 12), -3 % 12)              # -3.0 9
print((int(math.fmod(-3, 12)) + 12) % 12)      # 9  the portable fix

Division needs an inverse. Fermat's version and Python's built-in pow(b, -1, m) agree, and a value that shares a factor with the modulus has no inverse at all:

b = 123_456_789
inv = pow(b, MOD - 2, MOD)                     # Fermat: MOD is prime
print(inv == pow(b, -1, MOD), b * inv % MOD)   # True 1

a = b * 1_000_003                              # a / b is exactly 1_000_003
print((a % MOD) * inv % MOD)                   # 1000003
print((a % MOD) // (b % MOD))                  # 1  reducing, then dividing: wrong

try:
    pow(6, -1, 12)
except ValueError:
    print("ValueError")                        # ValueError  gcd(6, 12) is 6

def n_choose_k(n, k, mod=MOD):
    """Factorials and inverse factorials, all reduced as they are built."""
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i % mod
    return fact[n] * pow(fact[k], mod - 2, mod) * pow(fact[n - k], mod - 2, mod) % mod

print(n_choose_k(1000, 500) == math.comb(1000, 500) % MOD)   # True

Checked on 5,000 seeded random cases with exact big integers as the brute-force reference: every reduced sum, difference, product and power must equal the exact result reduced once at the end; every inverse must multiply back to 1; exact division through the inverse must match; and reducing before dividing must be caught getting it wrong:

import random

random.seed(26)
ok, wrong_division = True, 0
for _ in range(5_000):
    x, y = random.randint(-10**30, 10**30), random.randint(1, 10**30)
    ok &= (x + y) % MOD == ((x % MOD) + (y % MOD)) % MOD
    ok &= (x - y) % MOD == ((x % MOD) - (y % MOD)) % MOD
    ok &= (x * y) % MOD == ((x % MOD) * (y % MOD)) % MOD
    e = random.randint(0, 200)
    ok &= x**e % MOD == pow(x % MOD, e, MOD)
    q = random.randint(1, 10**12)
    if y % MOD:
        inv_y = pow(y, -1, MOD)
        ok &= y * inv_y % MOD == 1
        ok &= q % MOD == (y * q % MOD) * inv_y % MOD
        wrong_division += (y * q % MOD) // (y % MOD) != q % MOD
print(ok, wrong_division > 4_900)              # True True

The complexity

• Add, subtract, multiply, reduce: O(1) on machine words, which is the point of keeping values below m.
• Modular power and Fermat inverse: O(log e) multiplications.
• Factorial tables for n choose k: O(n) to build, then O(log m) per query, or O(1) with precomputed inverse factorials.
• Unreduced big integers: each operation costs time proportional to the number of digits, which keeps growing.

Where it goes wrong

• Reducing only at the end. Overflow has already happened in fixed-width languages; in Python it is correct but slow.
• Dividing reduced values. Multiply by the inverse instead, and only when it exists.
• Negative results in C-family languages. Add m before the final %.
• Overflow in the product. Two residues below 10^9 + 7 multiply to about 10^18; that needs a 64-bit type before the reduction.
• Comparing reduced values. a % m < b % m says nothing about a < b. Take a maximum before reducing, not after.

When it shows up in interviews

Any problem that says "modulo 10^9 + 7": counting paths, climbing stairs variants, combinations, and subsets. The same reduction appears in rolling hashes such as Rabin–Karp, in hash tables mapping a hash to a bucket, and in ring buffers wrapping an index. The Big-O cheat sheet lists fast exponentiation, the tool behind modular powers and Fermat inverses.

How to say it in an interview

"The true count overflows, so I reduce after every addition and multiplication; that is safe because adding whole multiples of the modulus does not change the remainder. Division does not survive reduction, so I multiply by a modular inverse, which exists here because 10^9 + 7 is prime: it is b to the power m - 2, by fast exponentiation. The modulus is small enough that a product of two residues fits in 64 bits. In a C-family language I would also add m before the final % to avoid a negative result."