Modular Arithmetic,
logic that never overflows

Section 1

Quick Reference

The whole page on one screen. Everything here is unpacked in full below. Watch for the marked lines: ★ trick · ⚠ pitfall · 💡 tip.

Section 2

Detailed Walkthrough

The trap. Your logic is right and the small cases pass, but on a big case the answer comes out negative — garbage where you expected trillions. Nothing in the logic is wrong. The true answer had hundreds of digits, a long holds ~19, and it silently wrapped around. That's why the problem says "print the answer modulo 10⁹+7": it hands you the one tool that keeps every intermediate value inside the box. The five habits below are the whole survival kit — each is just a way to reduce early and never let a value grow too large.

1. What "mod" actually is, and why problems ask for it

The modulo of a number is simply the remainder left over after division. 17 % 5 = 2, because 17 = 3×5 + 2.

The clock analogy. A 12-hour clock is arithmetic mod 12. It's 10 o'clock, you add 5 hours — not 15 o'clock, it's 3. The clock silently did 15 % 12 = 3. Every value on the face lives in 0..11 no matter how much time you add. Modular arithmetic is exactly this: a number line rolled into a circle of size m, where everything stays inside 0 .. m-1.

When a problem ends with "return the answer modulo 10⁹+7," it's telling you the true count is astronomically large — think number of ways to arrange things, which explodes factorially. Nobody can store or check a 100-digit number, so everyone compares just the remainder mod a fixed prime. If your remainder matches theirs, your logic was right.

2. int vs long, and the L suffix

Overflow is the whole game, so the first move is knowing exactly how much room each type gives you and typing the wide one on purpose. Anything that could grow past a couple billion goes in a long from the start — not an int you widen later.

Type	Holds up to	Named limit
int (32-bit)	~2.1 × 109 (231−1)	Integer.MAX_VALUE = 2147483647
long (64-bit)	~9.2 × 1018 (263−1)	Long.MAX_VALUE = 9223372036854775807

3. Why that exact number, and the "sweet spot"

10⁹+7 is often called a "sweet spot." Two properties earn it that name.

Property	What it buys you
It's prime	Every non-zero value has a modular inverse (Fermat needs a prime), so you can divide. Remainders are also "spread out" — fewer accidental collisions.
Sweet spot for size	Any value stays < 109+7. Add two → ~2×109 (still near int range). Multiply two → ~1018, which fits comfortably in a long (max 9.2×1018). So (a%M)*(b%M) never overflows a long.

The Five Rules

When you hit a modulo problem, run these

Rule 1Use long everywhere

The first defense is to never touch a 32-bit int for values that could grow. Declare the modulus and every running value as long from the start, so nothing has a chance to overflow before you reduce it.

long MOD = 1_000_000_007L;   // modulus as a long constant
long ans = 0, prod = 1;    // running values are long, not int

Rule 2Take two at a time

Never combine three or more factors before reducing. Multiply two, take % M, then bring in the next one.

Here's the danger: in (a * b * c) % M, the product a * b may already have overflowed before the * c or the % M ever runs. The modulo can't rescue a value that's already garbage. So fold in one factor at a time, reducing after each step.

// Rule 2 in Java: fold in one factor at a time
long temp = (a % MOD) * (b % MOD) % MOD;   // two at a time
temp = temp * (c % MOD) % MOD;             // then the third

The properties this rests on

Mod distributes over +, −, and × — reducing early only discards whole multiples of M, which never affect a remainder. That's why "two at a time" is legal.

Rule 3Never use Math.pow() — binary exponentiation

Math.pow() returns a double, which can't hold a large integer exactly and gives you no way to reduce mod M partway through. So (long) Math.pow(a, b) % MOD silently returns wrong answers for large exponents — rounding error, plus the value overflows before the modulo ever runs. The fix is to write the power yourself.

The naive fix is a loop — multiply a into the answer b times, reducing each step. That's O(b), too slow when b is up to 109.

// O(b) - correct but too slow for large b
long ans = 1;
for (int i = 0; i < b; i++) ans = ans * a % MOD;

Binary exponentiation computes ab % M in O(log b) by squaring the base and halving the exponent — because ab = (ab/2)2 when b is even, and you peel off one factor when b is odd.

Recursive version

The recursive form reads exactly like the math: base case b == 0 returns 1, an odd b peels off one factor, an even b squares the half.

static long MOD = 1_000_000_007L;

static long binpow(long a, long b) {
    if (b == 0) return 1;              // base case
    if ((b & 1) == 1)                    // b is odd
    return a % MOD * binpow(a, b - 1) % MOD;
    long temp = binpow(a, b / 2);        // b is even
    return temp * temp % MOD;
}

Iterative version (preferred in Java — no stack risk)

static long power(long a, long b) {
    a %= MOD;
    long res = 1;
    while (b > 0) {
        if ((b & 1) == 1) res = res * a % MOD;  // bit set → multiply in
        a = a * a % MOD;                        // square the base
        b >>= 1;                                 // next bit
    }
    return res;
}

Rule 4In modulo you don't divide — you take the inverse

Plain division breaks under a modulus: (12 / 6) % 10 = 2, but reducing first gives (12%10) / (6%10) = 2/6, which isn't even an integer. Remainders throw away the information division needs.

To divide by b under a modulus, multiply by b's modular inverse — the number that plays the role of 1/b, i.e. the x with (b · x) % M = 1.

A concrete example: find x so that (6 · x) % 7 = 1. Testing, 6 · 6 = 36, and 36 % 7 = 1 — so 6-1 = 6 under mod 7. Dividing by 6 becomes multiplying by 6. But guessing doesn't scale, which is where Fermat comes in.

The key formula is exactly this last step: the inverse of any a is aM-2, which you already know how to compute fast with binary exponentiation. So inv is a one-liner on top of power.

// modular inverse via Fermat (MOD must be prime)
static long inv(long x) {
    return power(x, MOD - 2);      // x^(M-2) % M  ==  x^-1
}
// then:  (a / b) % M   becomes   a * inv(b) % MOD

Rule 5Fix negatives when printing

The % operator can return a negative result when the left side is negative: -3 % 7 gives -3, not the mathematically clean 4. A negative remainder fails comparisons and corrupts later steps — and it's how a "correct" solution ends up printing a negative final answer.

// Rule 5 - the guaranteed-positive print
System.out.println(((ans % MOD) + MOD) % MOD);

Clean-thinking tricks

Small moves that keep the logic clean

The n(n+1)/2 trap

The sum 1 + 2 + ... + n = n(n+1)/2. The final answer fits fine, but the intermediate product n * (n+1) can overflow before you divide by 2. For n ≈ 3×109, n(n+1) already blows past a long.

static long tri(long n) {
    return (n % 2 == 0) ? (n / 2) * (n + 1) : n * ((n + 1) / 2);
}

Reaching the next multiple of k

x % k is how far past the last multiple of k you are, so k - (x % k) is the gap to the next one. If x is already a multiple that gives k (wrong — should be 0), so one outer % k fixes the edge case.

Goal	Java expression	Note
Round down to a multiple of k	(x / k) * k	integer division floors
Round up to a multiple of k	((x + k - 1) / k) * k	+k-1 forces round-up
Ceiling division ⌈x/k⌉	(x + k - 1) / k	"how many k-buckets hold x"
Steps up to next multiple	(k - x % k) % k	0 if already a multiple

Divide and remainder, read as a pair

The same two operators keep showing up as a clean way to think, not just to compute. For any x and a block size k: x / k tells you which block you're in and x % k tells you where inside it. Almost every "wrap it around", "which bucket", "flatten a grid", or "peel a digit" question is just this one idea in disguise.

You want	Expression	Why it reads cleanly
Is x even / odd?	(x & 1) == 0  /  (x & 1) == 1	the last bit is the parity; faster and clearer than x % 2
Next index on a ring of size n	(i + 1) % n	from the last slot it wraps to 0 on its own — no if
Previous index on that ring	(i - 1 + n) % n	the + n keeps it positive before the wrap (same guard as Rule 5)
Flatten grid cell (r, c) of width C	idx = r * C + c	walk a 2D grid with a single index
Un-flatten idx back to (r, c)	r = idx / C,   c = idx % C	division gives the row, remainder gives the column
Last digit / drop it	x % 10  /  x /= 10	peel digits right-to-left in a loop
Which bucket of size k	x / k  (offset x % k)	group values into fixed-size ranges

Worked Problem 1

All 5 rules in one expression

Compute Ans = (A + ((B − C)D) / (E × 100) − F × G) % (109+7), given 1 ≤ A..G ≤ 109. If the answer is a fraction P/Q, print P · Q-1 % M.

This is the capstone — every rule fires at once. Read it as a pipeline of temp values, each reduced immediately (Rule 2), powers via binary expo (Rule 3), the division as a multiply-by-inverse (Rule 4), and a final positive-print (Rule 5).

import java.util.Scanner;

public class Main {
    static long MOD = 1_000_000_007L;

    static long power(long a, long b) {
        a %= MOD; long res = 1;
        while (b > 0) {
            if ((b & 1) == 1) res = res * a % MOD;
            a = a * a % MOD; b >>= 1;
        }
        return res;
    }
    static long inv(long x) { return power(x, MOD - 2); }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong(), b = sc.nextLong(), c = sc.nextLong();
        long d = sc.nextLong(), e = sc.nextLong();
        long f = sc.nextLong(), g = sc.nextLong();

        long t  = ((b - c) % MOD + MOD) % MOD;   // (B-C), guard negative
        t = power(t, d);                        // (B-C)^D  (Rule 3)
        long t2 = (e % MOD) * 100 % MOD;         // E*100    (Rule 2)
        t = t * inv(t2) % MOD;                  // / (E*100) (Rule 4)
        t2 = f % MOD * (g % MOD) % MOD;         // F*G      (Rule 2)
        t = (a + t) % MOD;                      // + A
        t = (t - t2) % MOD;                     // - F*G
        System.out.println(((t % MOD) + MOD) % MOD);  // Rule 5
    }
}

Worked Problem 2

Geometric series sum, mod M

Compute F(x, n, m) = (1 + x + x2 + ... + xn) % m, with 1 ≤ x, n, m ≤ 109.

Summing term-by-term is O(n) — too slow. Notice this is a geometric progression (GP) with first term 1 and ratio x, so the closed form applies:

Now every rule shows up: the numerator's power needs binary expo (Rule 3), the −1 can go negative (Rule 5), and the division by (x−1) is a multiply-by-inverse (Rule 4). Two edge cases matter.

Case 1 — m is prime (Fermat inverse works)

static long gpSumPrime(long x, long n, long m) {
    MOD = m;                                  // power/inv use MOD
    if (x == 1) return (n + 1) % m;         // edge case (1)
    long num = ((power(x, n + 1) - 1) % m + m) % m;  // x^(n+1) - 1, guarded
    long den = ((x - 1) % m + m) % m;          // x - 1, guarded
    long ans = num * inv(den) % m;            // / (x-1) via inverse
    return ((ans % m) + m) % m;               // Rule 5
}

Case 2 — m is not prime

When you can't invert, avoid division entirely. Split the series in halves. For an even count of terms, S(k terms) = S(k/2) × (1 + xk/2); for odd, peel one term. This is O(log n) and uses only + and ×, so any modulus (prime or not) is fine.

// sum of 1 + x + ... + x^(cnt-1), i.e. cnt terms, mod m. No inverse needed.
static long gpTerms(long x, long cnt, long m) {
    if (cnt == 0) return 0;
    if (cnt == 1) return 1 % m;
    if ((cnt & 1) == 0) {                       // even: pair up the halves
        long half = gpTerms(x, cnt / 2, m);
        long factor = (1 + powMod(x, cnt / 2, m)) % m;
        return half * factor % m;
    } else {                                    // odd: last term + the rest
        return (gpTerms(x, cnt - 1, m) + powMod(x, cnt - 1, m)) % m;
    }
}
// call with cnt = n + 1 terms:  gpTerms(x, n + 1, m)
// powMod is binary exponentiation taking an explicit modulus m

Cheat flow

How to decide what to do

Open a problem and run this top to bottom — it's the 5 rules as a checklist.

Interview / Practice Q&A

Click to reveal. Answers sized to read aloud.

Why do problems ask for the answer modulo 10⁹+7 instead of the real number?

Because the true answer often grows factorially and can have hundreds of digits, which no primitive type stores. Everyone reduces mod a fixed prime so answers stay small and comparable. 10⁹+7 is chosen because it's prime (enabling division via inverse) and small enough that the product of two reduced values still fits in a 64-bit long.

How do you keep a value from overflowing when it can exceed a couple billion?

You declare the wide type by hand: use long for the modulus and every running value, and suffix big literals with L. Watch method boundaries — reading input as int and multiplying does the math in int space before widening, so read into long or cast the first operand with (long) a * b.

What does "take two at a time" mean and why is it necessary?

When multiplying three or more values, combine just two, reduce mod M, then bring in the next. In a * b * c, the product a*b can overflow a long before the % M ever runs, and mod can't fix an already-corrupted value. Folding one factor at a time keeps every intermediate below M×M, safely inside a long.

Why never use Math.pow() for modular powers in Java?

Math.pow returns a double, which can't exactly represent large integers and gives no way to reduce mod M during the computation, so it overflows and rounds wrong. Write binary exponentiation instead: square the base and halve the exponent for O(log b), reducing mod M each step. For a bulletproof-but-slower option, BigInteger.modPow works too.

How do you divide under a modulus, and why can't you divide directly?

You multiply by the modular inverse, because taking the remainder of numerator and denominator separately loses the information division needs (2/6 isn't an integer). When M is prime, the inverse of b is b^(M-2) % M by Fermat's little theorem, computed with binary exponentiation. So a / b becomes a * power(b, M-2) % M.

Your answer prints as a negative number. What's the fix?

The % operator returns a negative result when the left operand is negative (-3 % 7 is -3). Wrap the final answer as ((ans % M) + M) % M to force it into [0, M). Math.floorMod(ans, M) is a built-in one-liner that does the same thing.

Walk through the GP-sum problem. What breaks when x = 1 or m isn't prime?

The closed form (x^(n+1) - 1)/(x - 1) divides by x-1. If x=1 that's division by zero, but the series is just n+1 ones, so return (n+1) % m. If m isn't prime, Fermat's inverse is invalid, so avoid division entirely with an O(log n) divide-and-conquer that pairs the halves using only + and ×.

For the sum 1 to n, why halve the even factor before multiplying?

Exactly one of n and n+1 is even, so dividing that one by 2 first keeps the arithmetic exact and roughly halves the peak intermediate value — avoiding overflow that n*(n+1) would cause before the division. If the answer is needed mod a prime and n is enormous, reduce first and multiply by inv(2) instead.

Given x and k, how many steps until x is a multiple of k, and why the outer % k?

It's (k - x % k) % k. The inner x % k is how far past the previous multiple you are, so k minus that is the gap to the next one. The outer % k handles the case where x is already a multiple, returning 0 instead of k.

Key Takeaways

The through-line. Every rule here is one defense against the same enemy — a value growing past what a long can hold before you reduce it. Reduce early, square instead of looping, invert instead of dividing, and guard the sign on the way out. Once those become reflexes, modular problems stop being about arithmetic and start being about logic.