In a counter accumulating a product mod 1e9+7, why reduce after every multiply instead of at the end?

## Why counting problems carry a modulus at all A combinatorial counter — how many distinct configurations satisfy some constraint — produces answers that grow factorially or exponentially in the input size. The exact value for `n = 200` has hundreds of digits and does not fit in any machine word. Rather than force every solution to carry big-integer arithmetic, the convention is to ask for the answer *modulo* a fixed prime, almost always `1000000007`. That turns an unbounded number into one that fits in a machine word, and it makes the expected output a single comparable value. ## The congruence that licenses early reduction Modular reduction is compatible with addition, subtraction and multiplication: ``` (a + b) mod m == ((a mod m) + (b mod m)) mod m (a * b) mod m == ((a mod m) * (b mod m)) mod m ``` So pushing the reduction inside the loop does not perturb the final answer at all — it is an exact rewrite, not an approximation. Candidates sometimes hesitate here, worried they are "losing information". They are not: every value the loop cares about is already only defined up to congruence. ## What actually changes: the size of the intermediate Hold the two loops side by side. In the deferred version the running product is the *true* product, and its bit-width is the sum of the bit-widths of everything multiplied in so far. Multiply in ten values around a billion and you already need about 300 bits. In the reduced version, every operand entering a multiply is at most `m - 1`, so the product is at most `(m-1)^2`. With `m = 1000000007`, that is just under `10^18`, comfortably inside the roughly `9.2 * 10^18` a 64-bit signed accumulator holds. Reduce again and you are back below `m`, ready for the next iteration. The loop's intermediates are bounded no matter how many iterations run. That bound is the entire design. It is also why the conventional modulus sits just under `2^30`: two residues multiply to under `2^60`, which leaves headroom in a 64-bit word, while sums of two residues need only 31 bits. ## Two different failure modes What goes wrong when you defer depends on what a multiply means on your platform, and mainstream runtimes made genuinely different calls here. Python and Ruby promote transparently to arbitrary-precision integers: the deferred loop stays *correct*, but each multiply now costs time proportional to the operand sizes, so a loop that should be linear becomes markedly superlinear and the memory for the intermediate grows without bound. C, Java and Go use fixed-width machine integers: the deferred loop wraps silently at the word boundary with no signal at all, and the final reduction is applied to a number that lost its high bits many iterations ago. The second failure is the dangerous one — the program is fast, quiet and completely wrong, and small test inputs pass because they never reach the overflow threshold. Note what the wrapped value is *not*: it is a correct result modulo `2^64`, and knowing a number modulo `2^64` tells you nothing about it modulo `1000000007`, because the two moduli are coprime. There is no salvage step. ## Details that trip people up **Reduce the factor, not only the accumulator.** If the incoming term can itself exceed the modulus — a precomputed value, a user-supplied count, a sum you built elsewhere — reduce it before the multiply, or the product can exceed `m^2` and the width argument collapses. **Subtraction needs a second thought.** Inclusion-exclusion counters subtract. Two residues in `0..m-1` can produce a negative difference, and taking a remainder of an already-small negative number leaves it negative. Add the modulus back before continuing, or the next multiply propagates a negative value through the rest of the loop. **Division is not on this list.** The congruence above covers `+`, `-` and `*`. Dividing residues is a different operation entirely and needs a modular inverse. **Exponentiation follows the same discipline.** Raising to a power is repeated multiplication, so the same reduce-every-step rule applies at each squaring; the bound argument is unchanged. ## Sizing it yourself The general rule: if you are reducing modulo `m`, your accumulator must hold `(m-1)^2` for a multiply-based pipeline, or roughly `2m` for an addition-only pipeline. Work backwards from the accumulator width you have to the largest modulus you can afford, rather than picking a modulus and hoping. That calculation is what an interviewer is really probing when they ask why the reduction goes inside the loop.