P6217 Simple Number Theory Problem

You are given a sequence $a$ of length $n$. There are $q$ queries asking for the value of $\prod_{i=l}^r \operatorname{lcm}(a_i,x)$. The answer should be taken modulo $10 ^ 9 + 7$.

The first line contains two integers $n,q$. The second line contains $n$ integers $a_i$. The next $q$ lines each contain three integers $l,r,x$.

Output $q$ lines, one answer per line.

**[Sample Explanation]** For the second query in Sample 1, the answer is: $\quad \operatorname{lcm}(12,3) \times \operatorname{lcm}(8,3) \times \operatorname{lcm}(9,3)$ $= 12 \times 24 \times 9$ $= 2592$. ------------------ **[Constraints]** **This problem uses bundled testdata.** - For $100 \%$ of the testdata: $1 \le l \le r \le n$, $1 \le n,q,a_i,x \le 2 \times 10 ^ 5$. - **Detailed constraints:** | Subtask ID | $n,q ,a_i,x\le $ | Special Property | Score | | :--------: | :---------------: | :---------------------------------: | :---: | | $1$ | $100$ | None | $10$ | | $2$ | $2 \times 10 ^ 5$ | $a_i,x$ are primes, and any $a_i \neq x$ | $10$ | | $3$ | $5 \times 10 ^ 4$ | $a_i$ are primes | $15$ | | $4$ | $5 \times 10 ^ 4$ | $μ(a_i) \neq 0$ | $15$ | | $5$ | $5 \times 10 ^ 4$ | None | $25$ | | $6$ | $2 \times 10 ^ 5$ | None | $25$ | ------------------------- **[Notes]** - Sample 2 satisfies the special property of Subtask 2, Sample 3 satisfies the special property of Subtask 3, and Sample 4 satisfies the special property of Subtask 4. - $μ(x)$ is the Möbius function, defined as follows: Let $x = {p_1} ^ {q_1} \times {p_2} ^ {q_2} \times ... \times {p_k} ^ {q_k}$. $μ(x) =\begin{cases}1&x=1\\(-1) ^ k&q_1,q_2...q_k \le 1\\0&\text{otherwise}\end{cases}$. Note: $p_i$ are primes, and $q_i$ are positive integers. Translated by ChatGPT 5