LCM Queries on Array

You are given an array a of length \( n \). You need to answer \( Q \) queries. In each query, given two indices \( l \) and \( r \), compute the least common multiple (LCM) of the segment \( a_l, a_{l+1}, \ldots, a_r \). Since the result can be very large, output the answer modulo \( 10^9+7 \).

The LCM of two numbers \( x \) and \( y \) is defined as:

[ \operatorname{lcm}(x, y) = \frac{x \times y}{\gcd(x, y)} ]

For more than two numbers, the LCM is computed iteratively:

[ \operatorname{lcm}(a, b, c) = \operatorname{lcm}(\operatorname{lcm}(a, b), c) \quad \text{and so on.} ]

</p>

inputFormat

The first line contains two integers \( n \) and \( Q \) representing the number of elements in the array and the number of queries, respectively.

The second line contains \( n \) space-separated integers \( a_1, a_2, \ldots, a_n \).

Each of the next \( Q \) lines contains two integers \( l \) and \( r \) denoting a query.

Note: The array is 1-indexed.

outputFormat

For each query, output a single line containing one integer: the LCM of the specified subarray modulo \( 10^9+7 \).

sample

3 2
2 3 4
1 2
2 3

6
12

</p>