MathAlgorithmaka mod, clock arithmetic, 1e9+7, congruences

Modular Arithmetic

Do arithmetic on remainders: reduce after every add, subtract and multiply so results stay small, and use a prime modulus like 1e9+7 so division works.

▶ VisualizePattern: Math & Number TheoryPractice (4)
Progress

Overview

Two integers are congruent mod `m` when they leave the same remainder on division by m. Modular arithmetic works with these remainders: (a + b) mod m = ((a mod m) + (b mod m)) mod m, likewise for subtraction and multiplication. Division is *not* free — it requires a Modular Inverse, which exists only when the divisor is coprime to m.

Problems that say "return the answer modulo 10^9 + 7" exist because the true answer (a count or product) would have thousands of digits. 10^9 + 7 is chosen because it is prime (so every nonzero residue has an inverse and Fermat's little theorem applies), and it is small enough that the product of two residues (< 10^18) fits in a signed 64-bit integer, so a * b % m never overflows. 998244353 is the other common choice because 2^23 divides m - 1, which enables NTT-based convolution.

Rules of thumb: reduce after every operation, keep values in [0, m), and fix negative results after subtraction with ((a - b) % m + m) % m. Languages with truncating % (C++, Java, JavaScript, Go) return negative remainders for negative dividends; Python's % is always non-negative for positive m.

modulo1e9+7overflowcongruencenumber theory

Intuition

A mental model before the formal terms.

A 12-hour clock: 9 o'clock plus 5 hours is 2 o'clock, not 14. You never need to know how many full days have passed to answer "what time is it" — only the position on the dial. Modular arithmetic is doing all your sums on the dial. Multiplication is the same: 5 hours repeated 5 times lands at 25 mod 12 = 1. Division is the odd one out: "which time, repeated 3 times, gives 6" has two answers on a 12-hour dial (2 and 6), so it is only unambiguous when the step size shares no factor with the dial size.

How it works

  1. Addition: (a + b) % m. With a, b < m the sum is < 2m, safe in 64-bit for any m < 2^62.
  2. Subtraction: (a - b + m) % m to avoid negatives when a, b are already reduced; general form ((a - b) % m + m) % m.
  3. Multiplication: a * b % m. Requires a, b < m and m² < 2^63, i.e. m < ~3·10^9. For larger m use 128-bit intermediates or mulmod by doubling.
  4. Exponentiation: Fast Exponentiation with reduction at every step.
  5. Division by b: multiply by b^(m-2) mod m (prime m) or the extended-Euclid inverse — see Modular Inverse.
  6. Comparison and min/max are meaningless after reduction; never take the modulo of a quantity you still need to compare or sort.

Why it works

Write a = q_a·m + r_a and b = q_b·m + r_b. Then a + b = (q_a + q_b)·m + (r_a + r_b) and a·b = (…)·m + r_a·r_b, so the remainder of the result depends only on r_a and r_b. Reducing early therefore changes nothing about the final remainder.

Division needs an inverse because ab ≡ ac (mod m) does not imply b ≡ c unless gcd(a, m) = 1: e.g. 2·3 ≡ 2·9 (mod 12) but 3 ≢ 9. With a prime modulus, every a ≢ 0 is coprime, so cancellation always works.

Overflow bound: with residues below m = 10^9 + 7, a product is below (10^9 + 7)² ≈ 1.0000000140·10^18 < 9.22·10^18 = 2^63, so 64-bit signed arithmetic is exact.

Recognition

How to tell a problem wants this.

  • "Return the answer modulo 10^9 + 7" (or 998244353) — counting paths, subsequences, arrangements, or products that overflow.
  • Cyclic structures: rotations, circular arrays ((i + k) % n), days of the week, hashing (h = (h·B + c) mod m, see Rolling Hash (Polynomial Hashing)).
  • Divisibility questions: "is the sum divisible by k", "count subarrays whose sum is divisible by k" (prefix sums mod k — see Prefix Sum).
“modulo 10^9 + 7” → Math & Number Theory

Interactive visualization

Play, step, change the input. ← → and space work too.

Showing the closely related Fast Exponentiation visualization.

ee (binary)e & 1baseresult
131101·31
1/13Compute 3^13 mod 1000000007. Write the exponent in binary (1101): each 1-bit contributes base^(2^k), so we square the base once per bit instead of multiplying 13 times.
Current iterationBit is 1: multiply result by baseBit is 0: skip the multiplyFinished
PseudocodeLearn Fast Exponentiation →
1result = 1; base = base mod M
2while e > 0:
3  if e & 1: result = result · base mod M   # this bit is set
4  base = base · base mod M
5  e = e >> 1
6return result
Variables
base3
e13
result1
M1000000007
Complexity
best O(log n)
avg O(log n)
worst O(log n)
space O(1)
Speed

Pseudocode

1add(a, b) = (a + b) mod m
2sub(a, b) = (a - b + m) mod m
3mul(a, b) = (a * b) mod m           // a, b < m, m^2 fits
4div(a, b) = mul(a, inverse(b))      // needs gcd(b, m) = 1
5normalize(x) = ((x mod m) + m) mod m

Implementations

1# Modular arithmetic keeps every intermediate inside a fixed range, which is
2# what makes counting problems with astronomically large answers tractable.
3# The distributive laws hold for +, - and *; division needs an inverse.
4MOD = 1_000_000_007
5 
6 
71 · Addition and subtraction: one conditional each, no % needed
8def add_mod(a: int, b: int, mod: int = MOD) -> int:
9    s = a + b
10    return s - mod if s >= mod else s
11 
12 
13def sub_mod(a: int, b: int, mod: int = MOD) -> int:
14    d = a - b
15    return d + mod if d < 0 else d
16 
17 
182 · Multiplication: no overflow to worry about, integers are unbounded
19def mul_mod(a: int, b: int, mod: int = MOD) -> int:
20    return a * b % mod
21 
22 
233 · Normalising is a no-op in Python: % already follows the divisor's sign
24def norm(a: int, mod: int = MOD) -> int:
25    return a % mod  # already in [0, mod) for a positive mod, even if a < 0
26 
27 
284 · Running products stay bounded: reduce at every step, never at the end
29def factorial_mod(n: int, mod: int = MOD) -> int:
30    acc = 1 % mod
31    for i in range(2, n + 1):
32        acc = acc * i % mod
33    return acc
34 
35 
365 · Precomputed tables turn repeated queries into O(1) lookups
37def factorial_table(n: int, mod: int = MOD) -> list[int]:
38    f = [1 % mod] * (n + 1)
39    for i in range(1, n + 1):
40        f[i] = f[i - 1] * i % mod
41    return f
Walkthrough
  1. Python integers are unbounded, so a * b % mod is always exact — there is no overflow question to answer, and mul_mod is a one-liner.
  2. norm is effectively a no-op: Python % returns a result with the sign of the *divisor*, so -1 % 7 is already 6.
  3. factorial_mod still reduces every step. Not for correctness here, but for speed: an unreduced factorial of 10^5 has roughly half a million digits, and each further multiplication scales with that width.
  4. 1_000_000_007 uses numeric underscores, which are ignored by the parser and make the constant readable.
  5. f = [1 % mod] * (n + 1) is safe because integers are immutable; the same idiom with a list element would alias.
Complexity (this implementation)
time O(1) per operation for small residues; O(n) to build the table · space O(1) per operation; O(n) for the table

Reducing at every step is a genuine asymptotic improvement in Python, not a micro-optimisation — unreduced products grow without bound and multiplication cost grows with digit count.

Language notes
  • % follows the sign of the divisor, so a positive modulus always yields a non-negative residue — the one language here where negative normalisation is unnecessary.
  • divmod(a, b) returns quotient and remainder in one call and is faster than computing both separately.
  • math.factorial(n) % mod is exact but computes the full unreduced factorial first, which is enormous for large n.
  • pow(base, exp, mod) is the built-in modular exponentiation and is the right primitive for modular division.
Common mistakes in this language
  • Using math.factorial(n) % mod for large n, which allocates a number with hundreds of thousands of digits before reducing.
  • Adding a C-style negative-modulo guard that is redundant and misleads readers into thinking Python behaves like C.
  • Assuming the arbitrary precision makes reduction optional — it makes it *safe* to skip, not *cheap*.
Language differences that matter here
  • The sign of % splits the four cleanly: Python follows the divisor (always non-negative for a positive modulus), while C++, JavaScript and TypeScript follow the dividend and need explicit normalisation.
  • Overflow: Python has none, JS/TS avoid it by using BigInt (a compile error on mixing in TypeScript, a runtime TypeError in JavaScript), and C++ needs the non-standard __int128.
  • Reducing at every step is required for correctness in C++ and for tractability in Python and BigInt JS/TS — the same discipline for two different reasons.
  • Readable constants: C++14 1'000'000'007, Python and JS/TS 1_000_000_007 — same idea, different separator character.

Complexity

Best
O(1)
Average
O(1)
Worst
O(1)
Space
O(1)

Per add/sub/mul. Division costs O(log m) via a modular inverse. Python big-int operations grow with digit count, which reduction keeps bounded.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Any counting or product answer that the problem asks for "mod 10^9 + 7" — reduce at every step, never at the end.
  • Hashing and rolling hashes, pseudo-random generators, cyclic index arithmetic.
  • Divisibility counting via residues of prefix sums.
Avoid it when
  • When you need to compare, sort, or take the minimum of the true values — reduction destroys order. Compute with big integers or logarithms instead.
  • When the problem never mentions a modulus and values fit: unnecessary % operations are slow (integer division) and obscure the code.
  • Dividing by numbers that share a factor with the modulus — the inverse does not exist; restructure the computation (e.g. cancel factors before reducing).

Alternatives

Fast ExponentiationModular Inverse

Common mistakes

  • Reducing only at the end — the intermediate overflows long before.
  • Negative results from (a - b) % m in C++/Java/JS/Go; add m before reducing.
  • Multiplying two reduced 32-bit ints in a 32-bit type (int * int in Java/C++) — cast to 64-bit first.
  • JavaScript: a * b % m with a, b ≈ 10^9 silently loses precision above 2^53; use BigInt or split multiplication.
  • Using % to "divide" (x / y % m) — division must go through the modular inverse.
  • Choosing a composite modulus (10^9) and then needing inverses that do not exist.

Interview patterns

  • Count paths / subsequences / ways with DP mod 10^9 + 7.
  • Subarray sums divisible by k; continuous subarray sum with prefix remainders.
  • Rolling hash with a large prime modulus and base — see Rabin–Karp.
  • Modular combinatorics with precomputed factorials — see Combinatorics.

Example problems

Repeated DNA SequencesmediumSubarray Sum Equals KmediumUnique PathsmediumPow(x, n)medium