Range Products, Zeros Included

Difficulty: 1600 3500 ms 128 MB

math prefix-sums

Answer Q range-product queries modulo 10⁹+7 on an array that may contain ZEROS.

Input: the first line has N and Q; the second line has N non-negative integers; the next Q lines have L and R.

Output: Q lines: the product of a_L..R mod 10⁹+7.

Constraints:

• 1 ≤ N, Q ≤ 10⁵
• 0 ≤ a_i ≤ 10⁹

Sample Tests

5 2
2 3 0 4 5
1 2
2 4

6
0

1 1
0
1 1

0

Read the Editorial