IntermediateMath for DSADynamic Programming
Why answers are “mod 10⁹ + 7”
Counts can grow astronomically, so problems ask for the answer mod 10⁹+7. Take the mod after every + and ×, not just at the end.
The idea
Counting problems (number of ways, paths, strings) often have answers with hundreds of digits. To keep numbers small, the problem asks for the remainder mod 10⁹ + 7, a large prime that fits in 32 bits.
The rules that make it work: (a + b) % m = ((a % m) + (b % m)) % m, and the same for ×. So you can reduce after every step and the final remainder is still right. Subtraction needs care: (a − b) % m can go negative in Java/C++, so add m first.
Worked example
Ways to climb n stairs, mod 10⁹ + 7
- ways(i) = ways(i − 1) + ways(i − 2): Fibonacci, which grows past 64 bits around n = 93.
- Store (ways(i − 1) + ways(i − 2)) % MOD at every step instead.
- Every value stays below 10⁹ + 7, and the answer matches the true count's remainder.
In code (Python)
MOD = 10**9 + 7
def count_ways(n):
a, b = 1, 1
for _ in range(n - 1):
a, b = (a + b) % MOD, a
return a
def mul_mod(a, b):
return (a % MOD) * (b % MOD) % MODSame as without the mod; each step adds an O(1) remainder.
How to spot it
- “Return the answer modulo 10⁹ + 7.” It's a hint the answer is a huge count, usually from DP or combinatorics.
Common mistakes
- Taking the mod only at the end: in Java/C++ the intermediate values already overflowed.
- Dividing under a mod: you can't just divide; you need a modular inverse (see the fast power tip).
Where it comes up
Go further
Up next for you · Beginner
“Have I seen this?” is a set →