题目描述

给出一个长度为 $n$ 的序列 $a$，$q$ 次询问 $\prod_{i=l}^r \operatorname{lcm}(a_i,x)$ 的值。

答案对 $10 ^ 9 + 7$ 取模。

输入格式

第一行两个整数 $n,q$。

第二行 $n$ 个整数 $a_i$。

接下来 $q$ 行，每行三个整数 $l,r,x$。

输出格式

$q$ 行，一行一个答案。

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

提示

【样例解释】

对于样例一的第二个查询，答案是：

$\quad \operatorname{lcm}(12,3) \times \operatorname{lcm}(8,3) \times \operatorname{lcm}(9,3)$

$= 12 \times 24 \times 9$

$= 2592$

【数据范围】

本题采用捆绑测试。

• 对于 $100 \%$ 的数据：$1 \le l \le r \le n$，$1 \le n,q,a_i,x \le 2 \times 10 ^ 5$。

• 详细的数据范围：

  Subtask 编号	$n,q ,a_i,x\le$	特殊性质	分值
  $1$	$100$	无	$10$
  $2$	$2 \times 10 ^ 5$	$a_i,x$ 是质数，任意 $a_i \neq x$
  $3$	$5 \times 10 ^ 4$	$a_i$ 是质数	$15$
  $4$		$μ(a_i) \neq 0$
  $5$		无	$25$
  $6$	$2 \times 10 ^ 5$

【提示】

• 样例二满足 Subtask2 的特殊性质，样例三满足 Subtask3 的特殊性质，样例四满足 Subtask4 的特殊性质。

• $μ(x)$ 是莫比乌斯函数，它的定义如下：

  设 $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}$

  注：$p_i$ 为质数，$q_i$ 为正整数。