Working modulo 10⁹ + 7

Bits and maths Senior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
m = 1_000_000_007
b = 4
inv = pow(b, m - 2, m)
print(b * inv % m, (12 * inv) % m, (-3) % m)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 1 3 1000000004

Right: inv is 4's inverse, 12 / 4 = 3, and Python's % keeps the result non-negative.

Division under a prime modulus becomes multiplication by an inverse, computed in O(log m) with three-argument pow.

Why not the others?
  • B 1 3 -3. Python's % with a positive modulus never returns a negative number.
  • C 4 12 1000000004. Multiplying by the inverse undoes the multiplication by 4.

30-second answer

Counts like the ways to arrange or climb can grow past any fixed integer size. Reporting them modulo a large prime keeps numbers small. Addition, subtraction and multiplication can be reduced at every step: (a + b) % m and (a × b) % m. Division needs a modular inverse: pow(b, m - 2, m) when m is prime. Python never overflows, but reducing still keeps the numbers small and fast.

Practise saying it · 45 s. No recording, just a timer

Explain modular arithmetic for big counts.

Say your answer out loud, then check which of these points you covered:

  • Reduce every step
  • Inverse via pow(b, m - 2, m)
  • Watch negatives in Kotlin

Deep dive

Reduce after each operation, not only at the end, to keep intermediate values small.

In Kotlin or Java, use Long for products of two values below 10⁹ + 7.

(a - b) % m in Python is already non-negative; in Kotlin add m before taking %.

Common mistakes

  • Dividing directly instead of multiplying by the modular inverse.
  • Reducing only at the end, which in fixed-width languages overflows first.

Senior take & follow-ups

Say 'reduce at every step' and mention the inverse for division.

Follow-up questions

Think of your answer first, then open the hint.

  1. Why is m - 2 the inverse exponent?

    Show hint

    By Fermat's little theorem, b^(m - 1) ≡ 1 mod m for prime m, so b^(m - 2) is b's inverse.

  2. How do you compute n choose k modulo m?

    Show hint

    Precompute factorials and inverse factorials modulo m, then multiply.

What each operation costs: Hash Functions

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.