1370. The Product of a Range, Modulo m

Print l * (l+1) * (l+2) * ... * r reduced modulo m, as a value in 0 to m-1. The range is inclusive at both ends and holds at most 2001 values, but the values themselves run as high as 10^12.

l = 3, r = 6, m = 1000000007 -> 3*4*5*6 = 360 -> 360 l = 5, r = 5, m = 7 -> 5 -> 5

## What most people try first

acc = (acc * x) % m with x taken straight from the loop counter. Problem 1367 taught exactly that line, and here it is not enough, because the terms are no longer smaller than the modulus.

acc < m <= 10^9 x <= 10^12 acc * x <= 10^21

A signed 64-bit integer stops near 9.22 * 10^18, so 10^21 wraps. The wrap is silent and the printed residue is wrong by no obvious amount.

## Reduce the term before you use it

acc = 1 mod m for x from l to r: acc = (acc * (x mod m)) mod m

Now both factors are below m, so the product is below m^2, which is 10^18 and fits. One extra % per step buys three orders of magnitude of headroom.

## Why reducing the term first is allowed

x and x mod m differ by a multiple of m, and multiplying the accumulator by a multiple of m more or less changes the result only by a multiple of m. Formally (acc * x) mod m equals (acc * (x mod m)) mod m, which is the same rule used for the accumulator, applied to the other factor.

## The answer is often zero, and that is not a bug

If the range contains a multiple of m, that term reduces to 0 and the whole product is 0 from then on. For m = 1000000 and a range straddling 10^9 the answer really is 0. A loop that skips zero terms to "avoid losing the product" is wrong.

## Overflow

The ranges are capped at 2001 terms precisely so this problem is about the width of one multiplication and not about speed. In JavaScript a Number is exact only below 2^53, about 9 * 10^15, so both 10^12 inputs and products near 10^18 need BigInt.

## Cost

O(r - l + 1) multiplications, at most 2001 of them.

Constraints - `1 ≤ l ≤ r ≤ 1000000000000` - `r - l ≤ 2000` - `2 ≤ m ≤ 1000000000`