Modular Exponentiation

In competitive programming, you often need to compute $x^n \bmod m$ where $n$ is huge (like $10^9$).

Naive exponentiation would overflow. Even $2^{1000}$ has 300+ digits. But using modular arithmetic, you can keep numbers small while computing the correct result modulo $m$.

The trick: $(a \times b) \bmod m = ((a \bmod m) \times (b \bmod m)) \bmod m$. Apply this after every multiplication to prevent overflow.