Introduction

If you're new to the world of competitive programming, you may have noticed that some questions, typically combinatorial and probability questions, have this funny habit of asking you to calculate a huge number, then tell you that "because this number can be huge, please output it modulo $$$10^9 + 7$$$". Like, it's not enough that they ask you to calculate a number they know will overflow basic integer data types, but now you need to apply the modulo operation after that? Even worse are those that say you need to calculate a fraction $$$\frac pq$$$ and ask you to output $$$r$$$ where $$$r \cdot q = p \text{ mod } n$$$... not only do you have to calculate a fraction with huge numbers, how in the world are you going to find $$$r$$$?

Actually, the modulo is there to make the calculation easier, not harder. This may sound counterintuitive, but once you know how modular arithmetic works, you'll see why too. Soon you'll be solving these problems like second nature.

Terminology and notation

For convenience, I will define the notation $$$n \text{ mod } m$$$ (for integers $$$n$$$ and $$$m$$$) to mean $$$n - \lfloor \dfrac nm \rfloor \cdot m$$$, where $$$\lfloor x \rfloor$$$ is the largest integer that doesn't exceed $$$x$$$. This may or may not correspond to the expression n % m in your programming language (% is often called the "modulo operator" but in some instances, it's more correct to call it the "remainder operator"). If -8 % 7 == 6, you're fine, but if it is -1, you'll need to adjust it by adding $$$m$$$ to any negative results. If you use Java/Kotlin, the standard library function Math.floorMod(n, m) does what we need.

Also for convenience, I will also define the $$$\text{ mod }$$$ operator to have lower precedence than addition or subtraction, thus $$$ax + b\ \text{ mod } m \Rightarrow (ax + b) \text{ mod } m$$$. This probably does not correspond with the precedence of the % operator.

The value $$$m$$$ after the modulo operator is known as the modulus

"Basic" arithmetic

First off, some important identities about the modulo operator:

$$$(a \text{ mod } m) + (b \text{ mod } m)\ \text{ mod } m = a + b\ \text{ mod } m$$$

$$$(a \text{ mod } m) - (b \text{ mod } m)\ \text{ mod } m = a - b\ \text{ mod } m$$$

$$$(a \text{ mod } m) \cdot (b \text{ mod } m)\ \text{ mod } m = a \cdot b\ \text{ mod } m$$$

These identities have the very important consequence in that you generally don't need to ever store the "true" values of the large numbers you're working with, only their residue $$$\text{ mod } m$$$. You can then add, subtract, and multiply with them as much as you need for your problem, taking the modulo as often as needed to avoid integer overflow. You may even decide to wrap them into their own object class with overloaded operators if your language supports them, though you may have to be careful of any object allocation overhead. If you use Kotlin like I do, consider using the inline class feature.

But what about division and fractions? That's slightly more complicated, and requires a concept called the "modular multiplicative inverse". The modular multiplicative inverse of a number $$$a$$$ is the number $$$a^{-1}$$$ such that $$$a \cdot a^{-1}\ \text{ mod } m = 1$$$

But how do you actually find such a number? Bruteforcing all numbers to a prime number close to a billion will usually cause you to exceed the time limit. There are two faster ways to calculate the inverse: the extended GCD algorithm, and Fermat's little theorem. Though the extended GCD algorithm is more versatile and sometimes slightly faster, the Fermat's little theorem method is more popular, simply because it's almost "free" once you implement exponentiation, another useful operation to do, so that's what we'll cover here.

Fermat's theorem says that as long as the modulus $$$m$$$ is a prime number ($$$10^9 + 7$$$ is prime, and so is $$$998\ 244\ 353$$$, another common modulus in these problems, then $$$a^m \text{ mod } m = a \text{ mod } m$$$. Working backwards, $$$a^{m-1} \text{ mod } m = 1 = a \cdot a^{m-2}\ \text{ mod } m$$$, therefore the number we need is $$$a^{m-2} \text{ mod } m$$$.

Note that this only works for $$$a \text{ mod } m \neq 0$$$, because there is no number $$$0^{-1}$$$ such that $$$0 \cdot 0^{-1}\ \text{ mod } m = 1$$$

Multiplying $$$m-2$$$ times would still take too long; therefore a trick known as exponentiation by squaring is needed. It's based on the observation that for positive integer $$$n$$$, that if $$$n$$$ is odd, $$$x^n=x( x^{2})^{\frac{n - 1}{2}}$$$, while if $$$n$$$ is even, $$$x^n=(x^{2})^{\frac{n}{2}}$$$. It can be implemented recursively by the following pseudocode:

function pow_mod(x, n, m):
    if n = 0 then return 1
    if n is even:
        t := pow_mod(x, n/2, m)
        return t * t  mod m
    else:
        t := pow_mod(x, (n-1)/2, m)
        return t * t * x  mod m

Or iteratively as follows:

function pow_mod(x, n, m):
    if n = 0 then return 1
    y := 1
    while n > 1:
        if n is even:
            x := x * x  mod m
            n := n / 2
        else:
            y := x * y  mod m
            x := x * x  mod m
            n := (n – 1) / 2
    return x * y  mod m

Now that you know how to compute the modular multiplicative inverse, you can now define the division operator:

$$$a / b\ \text{ mod } m = a \cdot b^{-1}\ \text{ mod } m$$$

Congratulations! You have now mastered $$$\mathbb Z / p \mathbb Z$$$ field arithmetic! A "field" is just a fancy term from category theory for a set with the four basic operators (addition, subtraction, multiplication, division) defined in a way that works just like you've learned in high-school for the rational and real numbers (however division by zero is still undefined), and $$$\mathbb Z / p \mathbb Z$$$ is just a fancy term meaning the set of integers from $$$0$$$ to $$$p - 1$$$ treated as residues modulo $$$p$$$.

This also means that algebra works much like the way you learned in high school. How to solve $$$3 = 4x + 5\ \text{ mod } 10^9 + 7$$$? Simply pretend that $$$x$$$ is a real number and get $$$x = -1/2\ \text{ mod } 10^9 + 7 = 500000003$$$.

You can also now take advantage of combinatoric identities, like $$$\displaystyle \binom{n}{k} = \frac{n!}{k! (n-k)!}$$$. The factorials can be too big to store in their true form, but you can store their modular residues instead, then use modular multiplicative inverse to do the "division".

There are only a few things you need to be careful of, like:

• divisions through modular multiplicative inverse would be slower than the other operations ($$$O (\log m)$$$ instead of $$$O(1)$$$), so you may want to cache/memoize the inverses you use frequently in your program.

• comparisons (once you represent a number by its modulo residue, comparisons are generally meaningless, as your $$$1$$$ might "really" be $$$m + 1$$$, $$$10^{100} m + 1$$$, $$$-5m + 1$$$, or even $$$\dfrac {m + 2} {2}$$$)

• exponentiation (when evaluating $$$x^n \text{ mod } m$$$, you can't store $$$n$$$ as $$$n \text{ mod } m$$$. If $$$n$$$ turns out to be really huge, you need to calculate it modulo $$$\varphi(m)$$$ instead, where $$$\varphi$$$ stands for Euler's totient function. If $$$m$$$ is prime, $$$\varphi(m) = m - 1$$$. Note that this new modulus will then usually not be prime, thus "division" in it will not be reliable (you can still use the extended GCD algorithm, but only for numbers coprime to the new modulus), but you can still use the other three operators. In category theory, $$$\mathbb Z / n \mathbb Z$$$ is a "ring" rather than a "field" when $$$n$$$ isn't prime due to this loss.)

Puzzles

Here are some simpler puzzles that require a modulo answer:

1281C — Cut and Paste

1178C — Tiles

1248C — Ivan the Fool and Probability Theory

935D — Fafa and Ancient Alphabet