LCM Product Queries

You are given a sequence \(a\) of length \(n\). Your task is to answer \(q\) queries. For each query, given three integers \(l\), \(r\) and \(x\), compute the value:

\[ \prod_{i=l}^{r}\operatorname{lcm}(a_i,x)\pmod{10^9+7} \]

Recall that the least common multiple (\(\operatorname{lcm}\)) of two numbers \(a\) and \(b\) can be computed using the formula:

\[ \operatorname{lcm}(a,b)=\frac{a\times b}{\gcd(a,b)} \]

All answers should be given modulo \(10^9+7\).

inputFormat

The first line contains two integers \(n\) and \(q\) separated by a space, representing the length of the sequence and the number of queries.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) separated by spaces.

Each of the next \(q\) lines contains three integers \(l\), \(r\) and \(x\), describing a query.

outputFormat

For each query, output a single line containing the result of \(\prod_{i=l}^{r}\operatorname{lcm}(a_i,x)\) modulo \(10^9+7\).

sample

3 2
4 6 8
1 2 6
2 3 4

72
96