Description

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$.

Input Format

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 Format

Output $q$ lines, one answer per line.

5 5
12 8 9 14 21
1 5 2
1 3 3
3 5 7
1 5 6
2 3 7

1016064
2592
18522
9144576
3528

10 10
47 47 47 3 7 19 2 7 31 31 
1 3 53
4 4 61
2 8 73
6 7 53
1 5 47
2 5 73
5 6 71
7 7 67
4 7 83
1 9 59

456856666
183
802334105
106742
816245119
365992530
670453
134
871739899
194416112

10 10
2 13 13 2 3 17 11 19 19 7 
4 8 1
1 2 7
6 7 37
9 10 7
1 8 9
3 8 47
5 8 2
3 6 9
4 5 25
4 5 8

21318
1274
256003
931
819082258
40076077
170544
2899962
3750
192

10 10
14 39 31 30 3 21 19 17 35 2 
1 3 10
6 6 19
2 4 3
6 8 18
1 10 2
5 6 49
2 6 8
7 9 26
3 6 12
1 1 10

8463000
399
108810
13186152
23723126
21609
437603581
198696680
22498560
70

Hint

[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$
  $3$	$5 \times 10 ^ 4$	$a_i$ are primes	$15$
  $4$		$μ(a_i) \neq 0$
  $5$		None	$25$
  $6$	$2 \times 10 ^ 5$

[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