A bakery logs how its sourdough starter grows: during hour i the yeast population is multiplied by factors[i]. The head baker asks many questions of the form "by what factor did it grow from the start of hour l to the end of hour r?", i.e. factors[l] · factors[l+1] · ... · factors[r]. These products are astronomically large, so answer each one modulo MOD = 1_000_000_007.
Write growth_queries(factors: list[int], queries: list[tuple[int, int]]) -> list[int] returning one answer per query (l, r) (0-indexed, inclusive, l <= r), in order.
growth_queries([2, 3, 5, 7], [(0, 3), (1, 2), (2, 2)]) # [210, 15, 5]
growth_queries([10**12], [(0, 0)]) # [999993007] (10**12 % MOD)
Multiplying out every range is O(n) per query, which is too slow for 10^5 queries over 10^5 hours. With sums you would use prefix sums and subtract; with products under a prime modulus you use prefix products and divide, and division mod a prime means multiplying by a modular inverse. No factor is a multiple of MOD, so no prefix product is ever 0 mod MOD and every inverse exists.
Constraints: 1 <= len(factors) <= 10^5, 1 <= factors[i] <= 10^12, factors[i] % MOD != 0, 1 <= len(queries) <= 10^5, 0 <= l <= r < len(factors).
Show hint
Let pre[0] = 1 and pre[i+1] = pre[i] * factors[i] % MOD. Then the product over [l, r] is pre[r+1] * pow(pre[l], MOD - 2, MOD) % MOD.