题目描述

记 $1, 2, . . . , n$ 中与 $n$ 互质的数的个数为 $\varphi (n)$。

给定正整数序列 $a_1, a_2, . . . , a_n$, 请依次执行 $q$ 个操作，操作有以下三种类型：

1. 0 i x: 修改 $a_i$ 的值为 $x$;
2. 1 l r: 查询 $\varphi(a_l + a_{(l + 1)} + \cdots + a_r)$ 的值，对 $10^9 + 7$ 取模后输出；
3. 2 l r: 查询 $\varphi(a_l \times a_{(l + 1)} \times \cdots \times a_r)$ 的值，对 $10^9 + 7$ 取模后输出；

输入格式

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

第二行 $n$ 个正整数 $a_1, a_2, . . . , a_n$。

接下来 $q$ 行，每行三个整数 0 i x, 1 l r 或 2 l r。 保证 $1 ≤ i ≤ n$, $x ∈ N^*$, $1 ≤ l ≤ r ≤ n$。

输出格式

对于每次形如 1 l r 或 2 l r 的操作，输出一行表示答案。

样例 #1

样例输入 #1

5 10
1 3 5 7 9
1 2 4
0 3 3
1 1 4
2 1 4
0 3 4
2 1 3
0 4 5
1 3 5
1 1 5
2 1 5

样例输出 #1

8
6
36
4
6
10
144

提示

样例解释

初始序列为 $1, 3, 5, 7, 9$，依次进行的 $10$ 个操作如下：

1. 查询 $φ(3 + 5 + 7) = φ(15) = 8$，输出 $8$；
2. 修改 $a_3$ 的值为 $3$，此时的序列为 $1, 3, 3, 7, 9$；
3. 查询 $φ(1 + 3 + 3 + 7) = φ(14) = 6$，输出 $6$；
4. 查询 $φ(1 × 3 × 3 × 7) = φ(63) = 36$，输出 $36$；
5. 修改 $a_3$ 的值为 4，此时的序列为 $1, 3, 4, 7, 9$；
6. 查询 $φ(1 × 3 × 4) = φ(12) = 4$，输出 $4$；
7. 修改 $a_4$ 的值为 $5$，此时的序列为 $1, 3, 4, 5, 9$；
8. 查询 $φ(4 + 5 + 9) = φ(18) = 6$，输出 $6$；
9. 查询 $φ(1 + 3 + 4 + 5 + 9) = φ(22) = 10$，输出 $10$；
10. 查询 $φ(1 \times 3 × 4 × 5 × 9) = φ(540) = 144$，输出 $144$。

数据范围

每个测试点的数据规模及特点如下表：

表中“包含的操作类型”表示对应测试点中每个操作的第一个数的可能值，例如，包含的操作类型为“0,1”表示该测试点不会出现形如 2 l r 的操作。

对于全部测试点，$n ≤ 50000, q ≤ 100000$，操作 $0$ 的个数不超过 $20000$，所有的 $a_i$、操作 $0$ 中的 $i, x$ 及操作 $1, 2$ 中的 $l, r$ 均在给定的限制下内均匀随机生成。