Modular Arithmetic Basics

Quick Revisit

• USE WHEN: Problem says "print the answer modulo 10^9+7" or any modular output
• INVARIANT: (a op b) % m = ((a%m) op (b%m)) % m for op in {+, -, *}; division needs modular inverse
• TIME: O(log p) for modpow/modinv | SPACE: O(1)
• CLASSIC BUG: Forgetting mod after subtraction—(a - b) % m can go negative; fix: ((a - b) % m + m) % m
• PRACTICE: ../12-practice-ladders/01-ladder-1100-to-1400.md

Modular arithmetic keeps numbers small during computation—essential for every CP problem that says "print the answer modulo ${10}^9+7$." The pattern fingerprint is immediate: the moment you read "answer mod 10^9+7," reach for % MOD after every + and *. The mnemonic to burn in: "Mod after every op, or your answer will flop." Pierre de Fermat stated his little theorem in 1640; Carl Friedrich Gauss formalized the congruence notation in Disquisitiones Arithmeticae (1801). The idea is as old as clock arithmetic—after 12 comes 1, not 13—and that intuition is exactly what you need in a contest.

Difficulty: Beginner | CF Rating: 800–1300 | Prerequisites: Arrays & Strings, Complexity Analysis

Rating Progression

CF Rating	What you should know
1200	% MOD after every + and *; know the subtraction +MOD fix; use 1LL casts
1500	modpow for binary exponentiation; modinv via Fermat; precompute factorials
1800	mint struct for bug-free mod; DP transitions under mod; combinatorics with $(\genfrac{}{}{0ex}{}{n}{k})$
2100	Extended GCD for non-prime mod; NTT-friendly mod 998244353; matrix exponentiation for recurrences

---

Contents

• Rating Progression
• Intuition
• C++ Built-ins for Modular Arithmetic
• Implementation (Contest-Ready)
• Operations at a Glance
• Problem Patterns
• Contest Cheat Sheet
• Gotchas & Debugging
• Deep Dives
• Self-Test
• Debug-This Exercises
• When NOT to Use Modular Arithmetic
• Practice Problems
• Further Reading

---

Intuition

When the Numbers Explode

Start with a simple problem: "Compute the $n$-th Fibonacci number."

For small $n$ the obvious loop is fine:

  F(10)  =  55
  F(20)  =  6765
  F(30)  =  832040

Then the constraint says $n\le {10}^6$. You write the loop, submit—and it's wrong.

// BROKEN -- overflows
long long fib[1000001];
fib[0] = 0; fib[1] = 1;
for (int i = 2; i <= n; i++)
    fib[i] = fib[i-1] + fib[i-2];
cout << fib[n] << "\n";

Fibonacci grows faster than any built-in integer can handle:

  F(40)  =          102334155
  F(50)  =        12586269025       <-- already past int range (2.1 * 10^9)
  F(80)  =  23416728348467684       <-- still fits long long
  F(93)  = 12200160415121876738     <-- near long long max (9.2 * 10^18)
  F(94)  = overflow. garbage. wrong answer.

long long can't even hold $F(94)$. For $n={10}^6$, the true value has over 200,000 digits. No built-in integer type can store it—and the problem already knew that when it said:

"Print the answer modulo ${10}^9+7$."

But what does that actually mean, and how do you use it?

---

The Core Idea: Remainders Are Preserved Through Operations

Modular arithmetic lets you take the remainder after every single operation, and the final remainder is the same as if you computed the giant number first and took the remainder at the end.

Think of a clock. A 12-hour clock "wraps" after 12: if it's 10 o'clock and you wait 5 hours, you get 3, not 15. You never need to think about the number 15—you just know 10 + 5 wraps to 3.

Modular arithmetic is the same wrapping, but with modulus $M={10}^9+7$ instead of 12. After every addition or multiplication, you fold the result back into the range $[0,M-1]$. The intermediate values never get large, so they never overflow.

The clock analogy breaks down for division—you can't "unwrap" a clock by dividing. Division under mod requires a special trick (modular inverse), covered below.

Visualizing clock wrapping with $M=12$:

              12
            /    \
          11      1
         /          \
       10            2
       |    CLOCK     |
       9             3
         \          /
           8      4
            \    /
              5-6-7

  10 + 5 = 15 --> 15 % 12 = 3  (wraps around)
   8 + 9 = 17 --> 17 % 12 = 5  (wraps around)

The clock analogy captures the intuition, but let's see the wrapping more precisely on a number line.

---

Visual Walkthrough: Number-Line Wrapping

Imagine $M=7$. The number line wraps into a circle:

                    0
                  /   \
                6       1
                |       |
                5       2
                  \   /
                    4
                    |
                    3

Any integer maps to a position on this circle by taking % 7:

   number:   0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  ...
   mod 7:    0  1  2  3  4  5  6  0  1  2   3   4   5   6   0  ...

Now see addition in action. Suppose $a=5$, $b=4$, $M=7$:

   Giant way:  5 + 4 = 9,  then  9 % 7 = 2
   Mod way:    (5 % 7) + (4 % 7) = 5 + 4 = 9,  then  9 % 7 = 2
   Same answer: 2

Multiplication with $a=5$, $b=4$, $M=7$:

   Giant way:  5 * 4 = 20,  then  20 % 7 = 6
   Mod way:    (5 % 7) * (4 % 7) = 5 * 4 = 20,  then  20 % 7 = 6
   Same answer: 6

Now the Fibonacci example with $M={10}^9+7$:

  +------+-------------------+-------------------+
  | i    | fib[i] (no mod)   | fib[i] % MOD      |
  +------+-------------------+-------------------+
  |  0   |                 0 |                 0  |
  |  1   |                 1 |                 1  |
  |  2   |                 1 |                 1  |
  | ...  |       ...         |       ...          |
  | 50   |   12586269025     |    586269025       |
  | 93   | 12200160415...738 |    453973694       |
  | 94   |  OVERFLOW!        |    383666580       |  <-- still fine
  | 10^6 |  200,000+ digits  |    some 9-digit #  |  <-- still fine
  +------+-------------------+-------------------+

  With mod: every fib[i] stays in [0, 10^9+6].  No overflow.

The fix is one line:

fib[i] = (fib[i-1] + fib[i-2]) % MOD;

We've seen why modding works through examples and pictures. Now let's state the rules precisely.

---

The Formal Rules

Three identities make modular arithmetic work. For any modulus $M>0$:

+-------------------------------------------------------------------+
|                                                                   |
|  ADDITION:                                                        |
|    (a + b) % M  =  ((a % M) + (b % M)) % M                      |
|                                                                   |
|  MULTIPLICATION:                                                  |
|    (a * b) % M  =  ((a % M) * (b % M)) % M                      |
|                                                                   |
|  SUBTRACTION:                                                     |
|    (a - b) % M  =  ((a % M) - (b % M) + M) % M                  |
|                                                                   |
|  DIVISION:   (a / b) % M  !=  ((a % M) / (b % M)) % M           |
|    --> use modular inverse instead                                |
|                                                                   |
+-------------------------------------------------------------------+

The $+M$ in subtraction handles a C++ quirk covered in the next section.

These identities let you mod after every single operation. The intermediate value after each step is at most $(M-1{)}^2$ for multiplication, which for $M={10}^9+7$ gives about ${10}^{18}$—just fitting in long long.

The key insight that makes this click: you are not computing a giant number and then reducing it. You are computing in a different number system from the start—one where numbers only go from $0$ to $M-1$ and then wrap. Every +, -, * stays in this small world. The giant number never exists in your program. Once you see it this way, the % MOD after each operation stops feeling like bookkeeping and starts feeling like the definition of your arithmetic.

---

What the Code Won't Teach You

Formulas and working code are necessary but not sufficient. The real skill is the reflex to classify each arithmetic operation as mod-safe or mod-unsafe the moment you write it—before the silent overflow, before test 7, before the 2 AM penalty.

Operation-level audit—the real skill:

Before submitting any modular arithmetic solution, scan your code line by line and ask:

  +  addition?       --> did I mod the result?
  *  multiplication? --> is there a 1LL or __int128 cast?
  -  subtraction?    --> did I add MOD before the final %?
  /  division?       --> am I using modinv, NOT integer division?

If any answer is "no," you have a silent bug.

When to use mint vs raw operations:

The mint struct eliminates the entire class of forgot-to-mod bugs. Use it by default everywhere modular values appear.

Drop to raw ll operations only when you need micro-optimization (extremely rare) or when the mod varies per query. If you're doing raw mod arithmetic "because it's simpler," you're optimizing for the wrong thing—correctness first.

Precomputing inverses for factorials:

A single modinv(x) call is $O(\log M)$. Inside a loop of $n$ iterations, that's $O(n\log M)$.

For combinatorics with factorials, precompute inv_fact[i] in $O(n+\log M)$ total by computing inv_fact[n] = modinv(fact[n]) once, then working backwards: inv_fact[i] = inv_fact[i+1] * (i+1) % MOD. This optimization makes DP problems with binomial coefficients feasible.

With that understanding in place, here is how to recognize modular arithmetic problems at a glance.

---

Trigger Phrases: When to Reach for Modular Arithmetic

Use it when you see:

• "Print the answer modulo ${10}^9+7$" (or any prime mod)
• "Count the number of ways..."
• "Since the answer can be very large..."
• Large combinatorial values (paths, subsequences, arrangements)
• Any DP where the state can grow exponentially

Don't confuse it with:

• Problems asking for the exact answer (GCD, min, max, shortest path)—these never say "modulo."
• Floating-point problems—mod doesn't apply to real numbers.
• Problems where $n$ is small enough that the answer fits in long long and no "modulo" appears in the statement.

Now that you can recognize when mod is needed, let's see what C++ gives you out of the box.

---

C++ Built-ins for Modular Arithmetic

There is no STL function for modular operations—you build them yourself. But these built-in types are relevant:

Function / Type	Header	What it does	Notes
long long	built-in	64-bit integer, max $\approx 9.2\times {10}^{18}$	Holds $({10}^9+6{)}^2$
__int128	built-in (GCC)	128-bit integer	For mods up to $\sim {10}^{18}$
gcd(a, b)	<numeric>	Greatest common divisor (C++17)	Used by ext-GCD inverse
1LL	literal suffix	Forces long long arithmetic	Prevents int * int overflow

These built-ins handle storage; the next section builds the actual modular operations on top of them.

---

Implementation (Contest-Ready)

Minimal Contest Template

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll MOD = 1e9 + 7;

ll add(ll a, ll b) { return (a + b) % MOD; }
ll sub(ll a, ll b) { return ((a - b) % MOD + MOD) % MOD; }
ll mul(ll a, ll b) { return 1LL * a % MOD * (b % MOD) % MOD; }

ll modpow(ll base, ll exp, ll mod = MOD) {
    ll res = 1;
    base %= mod;
    // Invariant: res * base^exp = original base^original_exp (mod mod)
    while (exp > 0) {
        if (exp & 1) res = (__int128)res * base % mod;
        base = (__int128)base * base % mod;
        exp >>= 1;
    }
    return res;
}

ll modinv(ll a) { return modpow(a, MOD - 2); }

struct mint {
    ll v;
    mint(ll x = 0) : v((x % MOD + MOD) % MOD) {}
    mint operator+(mint o) const { return (v + o.v) % MOD; }
    mint operator-(mint o) const { return (v - o.v + MOD) % MOD; }
    mint operator*(mint o) const { return (__int128)v * o.v % MOD; }
    mint operator/(mint o) const { return *this * o.inv(); }
    mint inv() const { return modpow(v, MOD - 2); }
    mint pow(ll e) const { return modpow(v, e); }
    bool operator==(mint o) const { return v == o.v; }
    bool operator!=(mint o) const { return v != o.v; }
    friend ostream& operator<<(ostream& os, mint m) { return os << m.v; }
    friend istream& operator>>(istream& is, mint& m) {
        ll x; is >> x; m = mint(x); return is;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    // Example: Fibonacci mod 10^9+7
    mint a = 0, b = 1;
    // Invariant: a = F(i-2) mod MOD, b = F(i-1) mod MOD
    for (int i = 2; i <= n; i++) {
        mint c = a + b;
        a = b;
        b = c;
    }
    cout << b << "\n";
}

Fully Annotated Version

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll MOD = 1e9 + 7;   // 1000000007, a prime number

// --- Basic operations ---

// Addition: a + b can be at most 2*(MOD-1) < 2*10^9 < long long max
// One final % brings it into [0, MOD-1].
ll add(ll a, ll b) {
    return (a + b) % MOD;
}

// Subtraction: a - b can be negative in C++.
// C++ guarantees (a % m) has the same sign as a (since C++11).
// So (-3) % 7 = -3, not 4.  We add MOD to make it non-negative.
//
// Example:  a = 2, b = 5, MOD = 7
//   (2 - 5) % 7 = (-3) % 7 = -3      <-- C++ result
//   (-3 + 7) % 7 = 4 % 7 = 4         <-- correct mathematical result
ll sub(ll a, ll b) {
    return ((a - b) % MOD + MOD) % MOD;
}

// Multiplication: a * b can be up to (10^9)^2 = 10^18.
// long long max is ~9.2*10^18, so it fits -- but ONLY if both operands
// are already reduced mod MOD.
//
// DANGER: if a and b are `int`, the product (a * b) is computed as
// int * int = int, which overflows at 2*10^9.
// The 1LL cast forces long long arithmetic BEFORE the multiply.
//
// Example:  a = 999999999, b = 999999999
//   (int) a * b overflows!
//   1LL * a * b = 999999998000000001 -- fits in long long
ll mul(ll a, ll b) {
    return 1LL * a % MOD * (b % MOD) % MOD;
}

// --- Binary exponentiation (modpow) ---
//
// Computes base^exp % mod in O(log exp) time.
//
// Idea: write exp in binary.  For example, 2^13:
//   13 = 1101 in binary = 8 + 4 + 1
//   2^13 = 2^8 * 2^4 * 2^1
//
// We iterate over bits of exp from low to high.
// We maintain `base` which doubles each step: base, base^2, base^4, ...
// Whenever a bit is set, we multiply `res` by the current `base`.
//
// Trace for base=2, exp=10 (binary 1010), mod=1000:
//
//   Step | exp (bin) | bit set? | base    | res
//   -----+-----------+----------+---------+------
//     0  |  1010     |   no     |    2    |   1
//     1  |   101     |   yes    |    4    |   4
//     2  |    10     |   no     |   16    |   4
//     3  |     1     |   yes    |  256    |  24  (= 4*256 % 1000)
//
//   Answer: 2^10 % 1000 = 24   (verify: 1024 % 1000 = 24)  correct!
//
// Uses __int128 for the intermediate product so it works even if
// mod is up to ~10^18.
ll modpow(ll base, ll exp, ll mod = MOD) {
    ll res = 1;
    base %= mod;
    // Invariant: res * base^exp = original base^original_exp (mod mod)
    while (exp > 0) {
        if (exp & 1) res = (__int128)res * base % mod;
        base = (__int128)base * base % mod;
        exp >>= 1;
    }
    return res;
}

// --- Modular inverse ---
//
// We want a^(-1) mod M such that a * a^(-1) = 1 (mod M).
//
// By Fermat's little theorem, if M is prime and gcd(a, M) = 1:
//   a^(M-1) = 1  (mod M)
//   => a * a^(M-2) = 1  (mod M)
//   => a^(-1) = a^(M-2)  (mod M)
//
// Since MOD = 10^9+7 is prime, this always works for a != 0.
//
// For non-prime mod, use extended Euclidean algorithm instead.
// See: ../07-mathematics/03-extended-euclid-crt.md
ll modinv(ll a) {
    return modpow(a, MOD - 2);
}

// --- The mint struct ---
//
// A "modular integer" that handles mod automatically via operator
// overloading.  Instead of writing:
//
//   ll a = (x + y) % MOD;
//   ll b = 1LL * a * z % MOD;
//
// You write:
//
//   mint a = mint(x) + mint(y);
//   mint b = a * mint(z);
//
// This eliminates an entire class of bugs (forgetting to mod, forgetting
// the 1LL cast, forgetting the +MOD in subtraction).

struct mint {
    ll v;

    // Constructor: normalizes any long long to [0, MOD-1]
    mint(ll x = 0) : v((x % MOD + MOD) % MOD) {}

    // Arithmetic operators -- each returns a properly reduced mint
    mint operator+(mint o) const { return (v + o.v) % MOD; }
    mint operator-(mint o) const { return (v - o.v + MOD) % MOD; }
    mint operator*(mint o) const { return (__int128)v * o.v % MOD; }
    mint operator/(mint o) const { return *this * o.inv(); }

    // Compound assignment
    mint& operator+=(mint o) { return *this = *this + o; }
    mint& operator-=(mint o) { return *this = *this - o; }
    mint& operator*=(mint o) { return *this = *this * o; }
    mint& operator/=(mint o) { return *this = *this / o; }

    // Modular inverse and power
    mint inv() const { return modpow(v, MOD - 2); }
    mint pow(ll e) const { return modpow(v, e); }

    // Comparison and I/O
    bool operator==(mint o) const { return v == o.v; }
    bool operator!=(mint o) const { return v != o.v; }
    friend ostream& operator<<(ostream& os, mint m) { return os << m.v; }
    friend istream& operator>>(istream& is, mint& m) {
        ll x; is >> x; m = mint(x); return is;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // --- Demo: basic operations ---
    ll a = 1000000006, b = 5;
    cout << "add: " << add(a, b) << "\n";   // 4
    cout << "sub: " << sub(3, 5) << "\n";   // 10^9 + 5

    // --- Demo: Fibonacci with mint ---
    int n = 50;
    mint fa = 0, fb = 1;
    // Invariant: fa = F(i-2) mod MOD, fb = F(i-1) mod MOD
    for (int i = 2; i <= n; i++) {
        mint c = fa + fb;
        fa = fb;
        fb = c;
    }
    cout << "F(50) mod MOD = " << fb << "\n"; // 586269025

    // --- Demo: modular inverse ---
    mint x = 3;
    mint xi = x.inv();
    cout << "3 * 3^(-1) = " << x * xi << "\n"; // 1
}

---

Operations at a Glance

Here is a quick-reference for every modular operation and its cost:

Operation	Time	Space	Notes
add(a, b)	$O(1)$	$O(1)$	Both args must be in $[0,M-1]$
sub(a, b)	$O(1)$	$O(1)$	Handles negative C++ remainder
mul(a, b)	$O(1)$	$O(1)$	Args must be reduced or use 1LL
modpow(base, exp, mod)	$O(\log \text{exp})$	$O(1)$	Binary exponentiation
modinv(a)	$O(\log M)$	$O(1)$	Via Fermat; $M$ must be prime
mint operations	$O(1)$ each	$O(1)$	Except / which is $O(\log M)$

Toolbox assembled. Now the patterns you will actually encounter in contests.

---

Problem Patterns

"Print the Answer Modulo ${10}^9+7$"

Recognition: The problem statement literally says it. This is the bread-and-butter pattern.

Mod after every addition and every multiplication. Never let an intermediate value exceed long long.

ll ans = 0;
// Invariant: ans = sum of a[0]*b[0] + ... + a[i-1]*b[i-1], reduced mod MOD
for (int i = 0; i < n; i++)
    ans = (ans + 1LL * a[i] * b[i]) % MOD;
cout << ans << "\n";

CF examples: CF 1744D, CF 1278C

---

Counting with Powers of 2

Recognition: "How many subsets / binary strings / colorings?" The answer is often $2^n$ or $k^n$ mod $M$. Use modpow.

// Number of subsets of an n-element set
cout << modpow(2, n, MOD) << "\n";

CF examples: CF 630I, CF 1475D

---

DP with Modular Transitions

Recognition: Any DP where the number of states can be huge—paths in a grid, sequences, tiling. Each transition is an addition or multiplication under mod.

See Dynamic Programming Fundamentals for the DP side; here we focus on the mod mechanics.

// Number of paths in a grid (only right/down moves)
vector<vector<mint>> dp(n, vector<mint>(m, 0));
dp[0][0] = 1;
// Invariant: dp[i][j] = number of paths from (0,0) to (i,j), mod MOD
for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
        if (i > 0) dp[i][j] += dp[i-1][j];
        if (j > 0) dp[i][j] += dp[i][j-1];
    }
cout << dp[n-1][m-1] << "\n";

CF examples: CF 1716C, CF 1512E

---

Division under Mod (Modular Inverse)

Recognition: When you need to compute $\frac{a}{b}modM$, multiply $a$ by $b^{-1}=b^{M-2}modM$ (Fermat's little theorem, $M$ prime).

// Expected value = sum / count, but under mod
ll ans = 1LL * sum % MOD * modinv(count) % MOD;

CF examples: CF 1081C

---

Modular Fibonacci and Linear Recurrences

Recognition: Any linear recurrence $f(n)=c_{1}f(n-1)+c_{2}f(n-2)+\dots$ with "mod $M$" in the output. For small $n$ ($\le {10}^7$), a simple loop with mod works. For large $n$ ($\le {10}^{18}$), use matrix exponentiation.

// Simple loop for n <= 10^7
mint a = 0, b = 1;
// Invariant: a = F(i-2) mod MOD, b = F(i-1) mod MOD
for (int i = 2; i <= n; i++) {
    mint c = a + b;
    a = b; b = c;
}
cout << b << "\n";

See Matrix Exponentiation for $O(\log n)$.

CF examples: CF 1114D

---

If I Had 5 Minutes

Five bullets to reconstruct everything from scratch:

1. Mod after every + and *: (a + b) % MOD, 1LL * a * b % MOD. Never accumulate unmodded.
2. Subtraction needs +MOD: ((a - b) % MOD + MOD) % MOD—C++ % can return negative.
3. Division = multiply by inverse: a / b mod M = a * modpow(b, M-2) % M (M must be prime).
4. modpow in ~5 lines: square-and-multiply, $O(\log n)$. Memorize it cold.
5. Use mint struct: paste it, forget about manual %. Drop to raw ll only if TLE.

---

Contest Cheat Sheet

+------------------------------------------------------------------+
|  MODULAR ARITHMETIC CHEAT SHEET                                  |
+------------------------------------------------------------------+
|  const ll MOD = 1e9 + 7;                                        |
|                                                                  |
|  add:  (a + b) % MOD                                            |
|  sub:  ((a - b) % MOD + MOD) % MOD                              |
|  mul:  1LL * a % MOD * b % MOD           // 1LL prevents overflow|
|  pow:  modpow(a, n, MOD)                 // O(log n)            |
|  inv:  modpow(a, MOD - 2, MOD)           // MOD must be prime   |
|  div:  1LL * a % MOD * modinv(b) % MOD                          |
|                                                                  |
|  Common MOD values:                                              |
|    1000000007  (10^9+7)  -- prime, most common                   |
|    998244353             -- prime, NTT-friendly (= 119*2^23+1)   |
|                                                                  |
|  NEVER do (a / b) % MOD.  Use inverse.                           |
|  NEVER forget 1LL for int*int products.                          |
|  ALWAYS mod after EVERY + and * in a loop.                       |
+------------------------------------------------------------------+

Before You Code: Modular Arithmetic Checklist

Run through this before submitting any mod problem:

+------------------------------------------------------------------+
|  BEFORE-YOU-CODE CHECKLIST                                       |
+------------------------------------------------------------------+
|  [ ] 1. Is MOD defined as a constant (not 1e9+7 inline)?        |
|  [ ] 2. Every + and * followed by % MOD (or using mint)?        |
|  [ ] 3. Every subtraction uses ((a-b)%MOD+MOD)%MOD?             |
|  [ ] 4. Every division uses modinv, NOT integer division?        |
|  [ ] 5. Every int*int multiplication has 1LL or (ll) cast?      |
+------------------------------------------------------------------+

The cheat sheet tells you what to write. The next section tells you what goes wrong when you don't.

---

Gotchas & Debugging

C++ Modulo Can Be Negative

In C++ (since C++11), a % b has the same sign as a. Python gives the mathematically positive remainder; C++ does not. This is the #1 source of WA in modular problems for beginners.

cout << (-3 % 5);   // prints -3, not 2

Fix: always use ((a % M) + M) % M for subtraction, or use mint.

Specifically: (a - b) % MOD produces a negative result when a < b. Always write ((a - b) % MOD + MOD) % MOD.

// BUG: subtraction goes negative
int a = 3, b = 5;
int MOD = 1000000007;
cout << (a - b) % MOD;                   // prints -2  (WRONG)

// FIX: add MOD before taking remainder
cout << ((a - b) % MOD + MOD) % MOD;     // prints 1000000005  (CORRECT)

Why the fix works:

  Scenario: a=3, b=5, MOD=7

  Without fix:              With fix:
  3 - 5 = -2                (3 - 5) = -2
  -2 % 7 = -2               (-2 % 7 + 7) % 7
    |                             |
    v                             v
   NEGATIVE!              (-2 + 7) % 7 = 5  [ok]

  Number line:
  ----[-2]----0----[5]----[7]----
         |           |
         +- WRONG    +- CORRECT

Forgetting 1LL in Multiplication

a * b is computed in int arithmetic when both operands are int. The result overflows before being assigned to the long long variable. Even with long long operands near ${10}^9$, the product approaches ${10}^{18}$ and care is needed.

int a = 1000000000, b = 1000000000;
long long c = a * b;     // OVERFLOW! int * int = int, then assigned to ll
long long d = 1LL * a * b;  // correct: 1LL forces long long arithmetic

int a = 1000000006, b = 1000000006;
int MOD = 1000000007;

// BUG: int * int overflows before mod
int bad = (a * b) % MOD;                        // undefined behavior

// FIX 1: cast to long long first
long long good1 = ((long long)a * b) % MOD;     // correct

// FIX 2: use 1LL multiplier
long long good2 = (1LL * a * b) % MOD;          // correct

Modding at the Wrong Time

// WRONG: mod only at the end
ll ans = 0;
for (int i = 0; i < n; i++)
    ans += 1LL * a[i] * b[i];  // can overflow after ~9 iterations
ans %= MOD;

// RIGHT: mod inside the loop
ll ans = 0;
// Invariant: ans in [0, MOD-1] after each iteration
for (int i = 0; i < n; i++)
    ans = (ans + 1LL * a[i] * b[i] % MOD) % MOD;

Division Is Not Modular

// WRONG
ll ans = (a / b) % MOD;

// RIGHT
ll ans = 1LL * a % MOD * modinv(b) % MOD;

You cannot take mod before dividing. $15/3=5$, but $(15mod7)/3=1/3$, which is not an integer. Use the modular inverse.

Using the Wrong MOD Value

  1e9 + 7  = 1000000007.0  (a double!)
  (ll)(1e9 + 7) = 1000000007  (OK, but fragile)

  Prefer:  const ll MOD = 1000000007;   // exact integer literal

Writing 1e9 + 7 gives a double. It works as an initializer for const ll, but using it directly in expressions can introduce floating-point issues. Write the full integer literal to be safe.

Inverse of Zero

modinv(0) is undefined—there is no $x$ such that $0\cdot x\equiv 1$. If your code calls modinv(0), you have a logic bug upstream.

Debugging Tips

• WA on a mod problem? First check: are you modding after every addition and multiplication? Search your code for + and * without a nearby %.
• Negative output? You're doing subtraction without the +MOD fix.
• TLE on a mod problem? You might be computing modinv inside a loop. Precompute inverses if needed (see Combinatorics Basics).
• Stress test: generate random inputs, compute with Python (arbitrary precision), compare with your C++ output.

Mental Traps

"I'll just add % MOD at the very end." You plan to fix negatives with one final (ans + MOD) % MOD. But if intermediate subtractions produce negative values that get multiplied or added, the damage propagates. You must maintain $[0,M-1]$ after every operation, not just the last one.

  THE DAMAGE PROPAGATION TRAP

  ans = (a - b) * c % MOD

  Step 1:  a - b = -3         <-- negative!
  Step 2:  -3 * c = -3000000  <-- still negative
  Step 3:  -3000000 % MOD     <-- C++ keeps the sign: NEGATIVE OUTPUT

  +-----------------------------------------------+
  | FIX: mod after EVERY operation                |
  |                                               |
  |   tmp = ((a - b) % MOD + MOD) % MOD;          |
  |   ans = 1LL * tmp * c % MOD;                  |
  +-----------------------------------------------+

"Mod doesn't hurt, so I'll mod everywhere." This is mathematically correct—extra mod never changes the result. But it creates false security: you mod additions religiously but forget the 1LL cast on a multiplication, or you mod the numerator but then divide it (which is wrong).

Sprinkling % is not a substitute for understanding which operations are mod-safe. The real guarantee comes from structure and discipline, not volume of mod operators.

"Fermat's and extended GCD are interchangeable." Fermat's little theorem ($a^{-1}=a^{M-2}$) only works when $M$ is prime. Extended GCD works for any $M$ where $gcd(a,M)=1$. Always verify the problem's mod is prime before using Fermat's.

  INVERSE METHOD SELECTION

  Is MOD prime?
       |
       +--- YES --> Fermat: modpow(a, MOD-2)   O(log M)
       |
       +--- NO  --> Is gcd(a, MOD) == 1?
                       |
                       +--- YES --> Extended GCD   O(log M)
                       |
                       +--- NO  --> NO INVERSE EXISTS!

  Common primes:  10^9+7  [ok]    998244353  [ok]
  NOT prime:      10^9    [no]    10^6+3     check!

"The answer is small, so I don't need mod." The final answer might fit in long long, but intermediate values in a DP or summation can overflow. The problem says "modulo ${10}^9+7$" because the intermediate path can blow up.

  OVERFLOW TIMELINE

  Iteration:    1     2     3     ...    40
  Value:       10^9  10^18  ???         BOOM
               |     |
               |     +-- fits long long (barely)
               |
               +-- fits long long easily

  After ~9 multiplications of 10^9-scale values:
  +--------------------------------------------+
  | 10^9 * 10^9 = 10^18  (near ll max)        |
  | Add a few more and you OVERFLOW            |
  | MOD inside the loop, not after it!         |
  +--------------------------------------------+

The Mistake That Teaches

2:15 AM, Codeforces Round #XXX, Problem C.

You've got a DP on sequences. The recurrence is simple: dp[i] = dp[i-1] + dp[i-2] - dp[i-3]. You coded it in 4 minutes. Sample cases pass. You submit. Wrong Answer on test 7.

You stare at the code. The logic is right. You test locally—for small $n$ it matches brute force. For $n=200000$, your answer is... negative? That can't be right.

Then you see it:

// THE BUG
dp[i] = (dp[i-1] + dp[i-2] - dp[i-3]) % MOD;

The subtraction. dp[i-1] + dp[i-2] could be less than dp[i-3] (after mod reduction). The result goes negative. C++ % preserves the sign. Your entire DP is polluted from that point forward.

The fix:

// THE FIX -- add MOD before the final %
dp[i] = ((dp[i-1] + dp[i-2] - dp[i-3]) % MOD + MOD) % MOD;

Or, even better—switch to mint and the entire class of bugs vanishes:

// THE REAL FIX -- use mint and never worry again
mint dp[MAXN];
// Invariant: dp[i] = number of valid sequences of length i, mod MOD
for (int i = 3; i <= n; i++)
    dp[i] = dp[i-1] + dp[i-2] - dp[i-3];  // mint handles everything

Lesson: Subtraction under mod is the #1 silent killer. If you do any subtraction in a mod problem, either use mint or apply the +MOD fix immediately. Don't tell yourself "it won't go negative here"—it will, on test 7.

What Would You Do If...?

Scenario 1: "The problem says mod ${10}^9+9$ instead of ${10}^9+7$." Check: is ${10}^9+9$ prime? Yes, it is. So everything works the same—Fermat's inverse, modpow, mint. Just change the constant. Always verify primality of an unfamiliar mod (a quick Miller-Rabin or just check a table).

Scenario 2: "The problem says mod ${10}^6$, which is NOT prime." Fermat's little theorem does not work. You need the Extended Euclidean Algorithm for modular inverse, and it only exists when $gcd(a,{10}^6)=1$. If the problem requires dividing by an even number mod ${10}^6$, you may need to restructure your approach entirely (e.g., track numerator and denominator separately, or use CRT).

Scenario 3: "My solution gets TLE and I'm using mint everywhere." Profile first—mint adds only ~10–20% overhead (see the benchmark in Deep Dives below). If TLE is within that margin, try switching hot loops to raw ll operations while keeping mint for the rest. More likely the TLE is algorithmic, not from mint.

Those are the common failure modes. For deeper understanding of why things work, read on.

---

Deep Dives

Why ${10}^9+7$?

This specific number ($1000000007$) is used everywhere because:

1. It's prime—so Fermat's little theorem gives modular inverse.
2. $(M-1{)}^2<2^{63}$—the product of two reduced values fits in long long ($\approx {10}^{18}<9.2\times {10}^{18}$).
3. $M$ fits in int—saves memory in arrays.

The other common mod is $998244353=119\times 2^{23}+1$, chosen because it's NTT-friendly—its multiplicative group has a large power-of-2 factor, enabling fast polynomial multiplication.

Binary Exponentiation: Step by Step

Computing $2^{10}mod1000$:

Write $10$ in binary: $10=(1010{)}_2=8+2$.

So $2^{10}=2^8\times 2^2$.

  +------+----------+---------+----------+---------+
  | Step | exp (bin)|  bit=1? |  base    |  res    |
  +------+----------+---------+----------+---------+
  |  0   |  1010    |   no    |     2    |    1    |
  |  1   |   101    |   yes   |     4    |    4    |
  |  2   |    10    |   no    |    16    |    4    |
  |  3   |     1    |   yes   |   256    |   24    |
  +------+----------+---------+----------+---------+
                       (4 * 256 = 1024, 1024 % 1000 = 24)

  Result: 2^10 % 1000 = 24.   Verify: 1024 % 1000 = 24.  Correct!

Why is this fast? A naive loop does $n$ multiplications. For $n={10}^{18}$ that's ${10}^{18}$ steps—way too slow. Binary exponentiation does $\lfloor {\log }_{2}n\rfloor +1$ steps. For $n={10}^{18}$, that's about 60 multiplications.

  +---------------------+-------------------+
  |       exp           | Steps (approx)    |
  +---------------------+-------------------+
  |          10         |       4           |
  |       1,000         |      10           |
  |   1,000,000         |      20           |
  |  10^9               |      30           |
  |  10^18              |      60           |
  +---------------------+-------------------+

Modular Inverse: What and Why

We want to compute $\frac{a}{b}modM$, but mod and division don't commute—you can't just divide. Instead, find $b^{-1}$ such that $b\cdot b^{-1}\equiv 1(\mathrm{mod}M)$, then compute $a\cdot b^{-1}(\mathrm{mod}M)$.

Via Fermat's little theorem (when $M$ is prime):

$$a^{M-1}\equiv 1(\mathrm{mod}M)$$$$\Rightarrow a\cdot a^{M-2}\equiv 1(\mathrm{mod}M)$$$$\Rightarrow a^{-1}\equiv a^{M-2}(\mathrm{mod}M)$$

So modinv(a) = modpow(a, MOD - 2). One modpow call, $O(\log M)$.

Example: find $3^{-1}mod7$.

  3^(7-2) = 3^5 = 243
  243 % 7 = 243 - 34*7 = 243 - 238 = 5
  Check: 3 * 5 = 15,  15 % 7 = 1.  Correct!

Computing inverse by exponentiation—visual flow:

  Input: a = 3, MOD = 7 (prime)

  Step 1: modpow(3, 7-2 = 5)
          3^1=3, 3^2=9, 3^4=81, 3^5=243

  Step 2: 243 % 7 = 5
          243 - 34*7 = 243 - 238 = 5

  Step 3: Verify
          3 * 5 = 15
          15 % 7 = 1  [ok]

  Result: 3^(-1) = 5 (mod 7)

Via extended Euclidean algorithm—works even when $M$ is not prime, as long as $gcd(a,M)=1$. See Extended Euclid & CRT for the full implementation.

The mint Struct: Eliminating Manual Mod

Writing % MOD after every operation is tedious and error-prone. The mint struct in the Implementation section wraps a long long and overloads all arithmetic operators to apply mod automatically.

Before (manual mod):

ll a = (x + y) % MOD;
ll b = ((a - z) % MOD + MOD) % MOD;
ll c = 1LL * b * w % MOD;
ll d = 1LL * c * modpow(v, MOD - 2, MOD) % MOD;

After (with mint):

mint a = x + y;
mint b = a - z;
mint c = b * w;
mint d = c / v;

Same result, half the code, zero chance of forgetting a % MOD.

In a contest, paste the mint struct at the top of your template and use it wherever you'd use ll for modular values.

Fermat's Little Theorem: Visual Proof

Theorem: If $p$ is prime and $gcd(a,p)=1$, then $a^{p-1}\equiv 1(\mathrm{mod}p)$.

Proof by permutation argument:

Consider the set $S=\{1,2,3,\dots ,p-1\}$ modulo $p$.

Now multiply every element by $a$ (where $gcd(a,p)=1$):

$aS=\{a\cdot 1,a\cdot 2,a\cdot 3,\dots ,a\cdot (p-1)\}modp$

Claim: $aS$ is a permutation of $S$. Why?

• No element is zero (since $a\ne 0$ and $k\ne 0$ mod $p$, and $p$ is prime).
• All elements are distinct: if $a\cdot i\equiv a\cdot j(\mathrm{mod}p)$, then $i\equiv j$ (cancel $a$ because it has an inverse mod $p$).
• There are $p-1$ distinct nonzero elements—so it must be the same set.

Since $aS$ is a permutation of $S$, their products are equal:

$$\prod _{k=1}^{p-1}(a\cdot k)\equiv \prod _{k=1}^{p-1}k(\mathrm{mod}p)$$$$a^{p-1}\cdot (p-1)!\equiv (p-1)!(\mathrm{mod}p)$$

Since $p$ is prime, $(p-1)!\not\equiv 0(\mathrm{mod}p)$, so we can cancel it:

$$a^{p-1}\equiv 1(\mathrm{mod}p)◼$$

Concrete example with $a=3$, $p=5$:

  Original set S = {1, 2, 3, 4}

  Multiply each by 3 mod 5:
    3*1 = 3 mod 5 = 3
    3*2 = 6 mod 5 = 1
    3*3 = 9 mod 5 = 4
    3*4 = 12 mod 5 = 2

  Result: 3S = {3, 1, 4, 2} -- a permutation of {1, 2, 3, 4}  [ok]

  Products:
    Original:   1 * 2 * 3 * 4 = 24
    Multiplied: 3 * 1 * 4 * 2 = 24

  So: 3^4 * 4! = 4! (mod 5)
      3^4 = 1 (mod 5)

  Verify: 3^4 = 81, and 81 % 5 = 1  [ok]

  PERMUTATION DIAGRAM (a=3, p=5)

  Original:    1 ----> 3    (3*1 mod 5)
               2 ----> 1    (3*2 mod 5)
               3 ----> 4    (3*3 mod 5)
               4 ----> 2    (3*4 mod 5)

  +---+    +---+
  | 1 |--->| 3 |
  +---+    +---+
  | 2 |--->| 1 |
  +---+    +---+
  | 3 |--->| 4 |
  +---+    +---+
  | 4 |--->| 2 |
  +---+    +---+

  Every element in {1,2,3,4} appears exactly once on the right.
  This is why the products match and we can cancel (p-1)!

Extended GCD: Inverse for Non-Prime Mod

When MOD is not prime, Fermat's little theorem doesn't apply. Instead, use the Extended Euclidean Algorithm, which finds integers $x,y$ such that:

$$a\cdot x+M\cdot y=gcd(a,M)$$

If $gcd(a,M)=1$, then $a\cdot x\equiv 1(\mathrm{mod}M)$, so $x$ is the modular inverse of $a$.

If $gcd(a,M)>1$, no inverse exists. You cannot divide by $a$ modulo $M$.

  INVERSE EXISTENCE CHECK

  gcd(a, MOD) == 1?
       |
       +--- YES --> inverse exists, use extgcd
       |
       +--- NO  --> NO INVERSE! Restructure your approach.

  Examples:
    a=3,  MOD=10  --> gcd=1 --> inverse exists (3*7=21, 21%10=1, inv=7)
    a=4,  MOD=10  --> gcd=2 --> NO inverse (4*x can only be even, never 1 mod 10)
    a=7,  MOD=12  --> gcd=1 --> inverse exists (7*7=49, 49%12=1, inv=7)
    a=6,  MOD=12  --> gcd=6 --> NO inverse

Contest-ready Extended GCD:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// Returns gcd(a, b) and sets x, y such that a*x + b*y = gcd(a, b)
ll extgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    ll x1, y1;
    ll g = extgcd(b, a % b, x1, y1);
    // Invariant: b*x1 + (a%b)*y1 = g, so a*y1 + b*(x1 - a/b*y1) = g
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

// Modular inverse of a mod m (m need NOT be prime)
// Returns -1 if inverse doesn't exist
ll modinv_general(ll a, ll m) {
    ll x, y;
    ll g = extgcd(a, m, x, y);
    if (g != 1) return -1;  // no inverse
    return (x % m + m) % m;
}

int main() {
    // Example: inverse of 3 mod 10 (non-prime mod)
    ll inv = modinv_general(3, 10);
    if (inv == -1) cout << "No inverse\n";
    else cout << "3^(-1) mod 10 = " << inv << "\n";  // prints 7

    // Example: inverse of 4 mod 10 (doesn't exist)
    inv = modinv_general(4, 10);
    if (inv == -1) cout << "4 has no inverse mod 10\n";  // prints this
    else cout << "4^(-1) mod 10 = " << inv << "\n";
}

When to use which method:

Scenario	Method	Complexity
MOD is prime	Fermat: modpow(a, MOD-2)	$O(\log M)$
MOD is not prime, $gcd(a,M)=1$	Extended GCD	$O(\log M)$
$gcd(a,M)>1$	No inverse—restructure	N/A
Need many inverses mod prime	Precompute: inv[i] = -(MOD/i) * inv[MOD%i] % MOD	$O(n)$ total

See Extended Euclid & CRT for the full derivation and Chinese Remainder Theorem applications.

mint vs Raw Ops Benchmark

The mint struct prevents bugs by handling % MOD automatically. But does it cost performance?

Benchmark: 10^8 modular multiply-accumulate operations

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;

struct mint {
    ll v;
    mint(ll x = 0) : v((x % MOD + MOD) % MOD) {}
    mint operator+(mint o) const { return (v + o.v) % MOD; }
    mint operator*(mint o) const { return (__int128)v * o.v % MOD; }
};

int main() {
    const int N = 100000000;

    // --- Raw ll benchmark ---
    {
        auto t0 = chrono::high_resolution_clock::now();
        ll ans = 0;
        // Invariant: ans = sum of i^2 for i in [1..j], reduced mod MOD
        for (int i = 1; i <= N; i++)
            ans = (ans + 1LL * i * i) % MOD;
        auto t1 = chrono::high_resolution_clock::now();
        double ms = chrono::duration<double, milli>(t1 - t0).count();
        cout << "Raw ll:  " << ans << "  (" << ms << " ms)\n";
    }

    // --- mint benchmark ---
    {
        auto t0 = chrono::high_resolution_clock::now();
        mint ans = 0;
        // Invariant: ans = sum of i^2 for i in [1..j], reduced mod MOD
        for (int i = 1; i <= N; i++)
            ans = ans + mint(i) * mint(i);
        auto t1 = chrono::high_resolution_clock::now();
        double ms = chrono::duration<double, milli>(t1 - t0).count();
        cout << "mint:    " << ans.v << "  (" << ms << " ms)\n";
    }
}

Typical results (compiled with g++ -O2):

  +-------------+--------+----------+
  | Method      |  Time  | Overhead |
  +-------------+--------+----------+
  | Raw ll ops  | ~320ms |   0%     |
  | mint struct | ~370ms |  ~15%    |
  +-------------+--------+----------+

  (10^8 multiply-accumulate operations, varies by machine)

Verdict:

  +-----------------------------------------------------------+
  | USE mint:                                                  |
  |   - During contests (ALWAYS default choice)               |
  |   - When correctness matters more than 50ms               |
  |   - When the problem has subtraction under mod             |
  |   - When you're writing DP with many transitions           |
  |                                                            |
  | USE raw ll ops:                                            |
  |   - TLE by a small margin and you've already optimized    |
  |     the algorithm                                          |
  |   - Hot inner loop with 10^8+ iterations                   |
  |   - MOD varies per query (mint hardcodes the constant)     |
  +-----------------------------------------------------------+

The ~15% overhead from mint is almost never the difference between AC and TLE. An algorithmic improvement (e.g., reducing $O(n^2)$ to $O(n\log n)$) dwarfs any mint overhead. Use mint by default. See Complexity Analysis for understanding when constant-factor optimization actually matters.

---

Self-Test

Before moving on, verify you can do these without looking above:

• [ ] Write the correct modular subtraction formula that handles C++ negative remainders.
• [ ] Explain why int a = 1e9; int b = 1e9; ll c = a * b; gives a wrong result, and write the one-character fix.
• [ ] Compute $3^{-1}mod7$ by hand using Fermat's little theorem.
• [ ] Explain why (15 / 3) % 7 gives 5 but (15 % 7) / 3 gives 0—and what you should do instead.
• [ ] State the two conditions required for Fermat's inverse to work (prime mod, $gcd(a,M)=1$).
• [ ] Given a loop that accumulates ans += a[i] * b[i], identify the two bugs (missing 1LL, missing % MOD inside the loop).

---

Debug-This Exercises

Find and fix the bug in each snippet. Answers are below (hidden by a spoiler-style separator).

Bug 1: The Silent Overflow

int n = 100000;
int a[100001], b[100001];
// ... fill a and b with values up to 10^9 ...
long long ans = 0;
for (int i = 0; i < n; i++)
    ans = (ans + a[i] * b[i]) % MOD;  // <-- bug here
cout << ans << "\n";

Bug 2: The Negative Ghost

ll dp[1001];
dp[0] = 1;
for (int i = 1; i <= n; i++)
    dp[i] = (dp[i-1] * 2 - dp[i-3]) % MOD;  // <-- bug here (assume i>=3)

Bug 3: The Division Trap

ll total = 1;
for (int i = 1; i <= n; i++)
    total = total * i % MOD;
// Compute total / k! mod MOD
ll kfact = 1;
for (int i = 1; i <= k; i++)
    kfact = kfact * i % MOD;
cout << (total / kfact) % MOD << "\n";  // <-- bug here

Bug 4: The Double Mod Miss

ll ans = 0;
for (int i = 0; i < n; i++) {
    ll term = 1LL * a[i] * b[i] % MOD;
    ll other = 1LL * c[i] * d[i] % MOD;
    ans += term + other;  // <-- bug here
}
ans %= MOD;

---

Answers:

Bug 1: a[i] * b[i] is int * int, which overflows before the % MOD. Fix: (ans + 1LL * a[i] * b[i]) % MOD—the 1LL forces long long multiplication.

Bug 2: dp[i-1] * 2 - dp[i-3] can go negative. C++ % preserves the sign. Fix: dp[i] = ((dp[i-1] * 2 - dp[i-3]) % MOD + MOD) % MOD;

Bug 3: total / kfact is integer division, not modular division. After mod reduction, total might be smaller than kfact, giving 0. Fix: cout << 1LL * total % MOD * modinv(kfact) % MOD << "\n";

Bug 4: ans += term + other accumulates without mod. After $n={10}^9$ iterations, ans overflows long long. Fix: ans = (ans + term + other) % MOD; inside the loop.

---

When NOT to Use Modular Arithmetic

Modular arithmetic is powerful but not always appropriate. Before reaching for % MOD, check whether the problem actually calls for it. See also the Data-Structure Selection Guide for choosing the right tool under pressure.

Situation	Why mod is wrong	What to do instead
Problem asks for exact answer (min, max, GCD, shortest path)	Mod destroys order relations: $a<b$ does NOT imply $amodM<bmodM$	Use regular arithmetic; check if long long or __int128 suffices
Comparing two values under mod	$a\equiv b(\mathrm{mod}M)$ does NOT mean $a=b$	If you need equality checks on actual values, don't mod
Floating-point or real-valued answers	Mod is only defined for integers	Use double/long double; see problem constraints
Answer fits in long long and problem doesn't say "modulo"	Unnecessary mod adds complexity and bugs	Just compute directly
You need to recover the original number from its mod	Modular reduction is lossy—you can't "undo" it	Store the original value separately if needed
Greedy/sorting based on values	Mod changes relative ordering of elements	Apply mod only to the final output, not to comparison keys

Key principle: Mod is a lossy projection. It preserves sums and products but destroys magnitude, ordering, and divisibility information. Use it only when the problem explicitly asks for it.

See also: Bit Manipulation for problems where bitwise operations (not mod) keep numbers manageable, and Prefix Sums for accumulation patterns that may or may not need mod depending on constraints.

For graded practice applying these ideas, work through the Practice Ladder (1100–1400).

---

Practice Problems

#	Problem	Source	Difficulty	Key Idea
1	CSES -- Exponentiation	CSES	Easy	Direct modpow
2	CSES -- Exponentiation II	CSES	Easy	Modpow with Fermat (reduce exponent mod $M-1$)
3	CF 1744D -- Divisibility by 2^n	CF	1200	Mod reasoning with powers of 2
4	CF 1475D -- Cleaning the Phone	CF	1800	Sort + greedy, careful with large sums
5	CSES -- Counting Rooms	CSES	Easy	BFS/DFS counting (warm-up for modular counting)
6	CF 1512E -- Permutation by Sum	CF	1600	Constructive + modular reasoning
7	CSES -- Fibonacci Numbers	CSES	Medium	Fibonacci mod ${10}^9+7$, matrix expo for large $n$
8	CF 1278C -- Berry Jam	CF	1400	Prefix computation with modular hashing

---

Recap

The essentials, compressed:

• Mod after every + and *—never accumulate unmodded values.
• Subtraction needs +MOD—C++ % can go negative.
• Division = multiply by inverse—modpow(b, MOD-2) when MOD is prime; Extended GCD otherwise.
• Use mint in contests to eliminate forgot-to-mod bugs at ~15% overhead.
• Recognize the trigger: "answer modulo 10^9+7", "count the number of ways", any DP with exponentially many states.
• Audit every arithmetic op before submitting: + modded? * has 1LL? - has +MOD? / uses inverse?

---

Further Reading

• cp-algorithms: Modular arithmetic—modular inverse, extended GCD, applications.
• cp-algorithms: Binary exponentiation—modpow and its many uses beyond simple exponentiation.
• Math Fundamentals—deeper coverage of modular arithmetic, GCD/LCM, and the full modular toolkit.
• Combinatorics Basics—precomputed factorials, $(\genfrac{}{}{0ex}{}{n}{r})$ under mod, inclusion-exclusion.
• Extended Euclid & CRT—modular inverse for non-prime moduli, Chinese Remainder Theorem.
• Number Theory—primes, sieve, Euler's totient, multiplicative functions.
• Bit Manipulation—bitwise tricks that complement modular arithmetic in many contest problems.
• FFT / NTT—why 998244353 is the other common mod (NTT-friendly), and fast polynomial multiplication under mod.
• Dynamic Programming Fundamentals—DP transitions are the most common place you'll apply modular arithmetic.

---

Next Up: Recursion and Backtracking—learn to break problems into subproblems, the foundation for DP and divide-and-conquer where modular arithmetic is heavily used.