Introduction

If you're new to the world of competitive programming, you may have noticed that some 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 that it's easier than it may seem at first.

Terminology and notation

For convenience, I will define the notation $$$n \text{ mod } 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.

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$$$.