If your program is correct but the judge keeps rejecting it on big inputs, the culprit is almost always overflow — and the cure is modular arithmetic.
Open almost any USACO Gold or Codeforces problem that asks "count the number of ways" and you will see the same instruction: print the answer modulo 109+7. That is not an arbitrary quirk. Counting and combinatorics problems produce answers far too large to fit in a 64-bit integer, so setters ask you to report the remainder after dividing by a large prime. Modular arithmetic is the toolkit that lets you compute with those remainders accurately and quickly.
What modular arithmetic actually means
Working "mod m" means numbers wrap around when they reach the modulus, the way a 24-hour clock returns to 0 after 23. Two numbers are equivalent if they leave the same remainder when divided by m. The crucial property for contestants is that the modulus distributes cleanly over the basic operations:
- Addition:
(a + b) % m = ((a % m) + (b % m)) % m - Subtraction: add
mbefore taking the mod so the result never goes negative - Multiplication:
(a * b) % m = ((a % m) * (b % m)) % m
Because the modulus survives every step, you can apply it after each operation instead of waiting until the end. That keeps intermediate values small and prevents the silent overflow that wrecks otherwise-correct solutions. The standard discipline: store everything as a 64-bit type, reduce after every multiply, and pick 1e9+7 (or 998244353) as the modulus because both are primes that fit comfortably in a long.
The two techniques you will reuse constantly
Fast (binary) exponentiation
Many problems need ab mod m where the exponent is enormous. Multiplying b times is hopeless. Instead, exponentiation by squaring computes the power in O(log b) time by repeatedly squaring the base and combining only the pieces selected by the bits of the exponent. It is short to write, hard to get wrong once memorized, and shows up in number-theory and combinatorics tasks alike.
Modular inverse
You cannot simply divide under a modulus — there is no such thing as 5 / 3 mod m by ordinary division. Instead you multiply by the modular inverse, the value a-1 satisfying a · a-1 ≡ 1 (mod m). The inverse exists only when gcd(a, m) = 1. When the modulus is a prime p, Fermat's Little Theorem gives it almost for free: a-1 ≡ ap-2 (mod p). In other words, one call to your fast-exponentiation routine produces the inverse — which is exactly why that routine is worth memorizing first. The alternative, the extended Euclidean algorithm, also works and does not require a prime modulus.
Where this shows up in real contests
Modular arithmetic is a gatekeeper skill on the path from beginner to medalist. In the USA Computing Olympiad, contestants progress through Bronze, Silver, Gold, and Platinum divisions; everyone starts in Bronze and earns promotion by scoring well. Modular techniques become essential around the Gold tier, where combinatorial counting and dynamic programming routinely return answers modulo a large prime. (Formats, contest windows, and eligibility change each season, so always confirm current details on the official competition pages.)
A practical study sequence looks like this:
- Implement safe modular add, subtract, and multiply, and test them against overflow-prone inputs.
- Write binary exponentiation and verify it on known powers.
- Use Fermat's Little Theorem to get inverses, then precompute factorials and inverse factorials so you can answer binomial-coefficient queries in O(1).
- Drill counting problems until reducing after every operation becomes reflex.
Treat 1e9+7 not as a magic number to memorize, but as a signal: the answer is a count, and your job is to make every arithmetic step modular from the start.
Modular arithmetic rewards deliberate practice more than raw talent. At BIAA's competitive programming program, students build these primitives from scratch and then apply them to graded problem sets, with a clear runway toward Olympiad-level contests. Ready to turn "modulo 1e9+7" from a mystery into muscle memory? Explore the program and start building.