Prefix Products Queries

Given an array of integers and several queries, your task is to calculate the product of a subarray for each query modulo (10^9+7). In each query, you are given two indices (L) and (R), and you must compute the product of elements from index (L) to (R) (both inclusive) modulo (10^9+7). To solve this efficiently, you should precompute prefix products so that each query can be answered in constant time.

The input is provided via standard input and the output must be printed to standard output. This problem requires careful handling of modular arithmetic and efficient input/output operations.

inputFormat

The first line contains a single integer (N), the number of elements in the array.\nThe second line contains (N) space‐separated integers representing the array elements.\nThe third line contains a single integer (Q), the number of queries.\nEach of the next (Q) lines contains two integers (L) and (R) describing a query.

outputFormat

For each query, output a single line containing the product of the subarray from index (L) to (R), taken modulo (10^9+7).## sample

1
5
1
1 1

5