欧拉函数

题目描述:

对于正整数 n，定义欧拉函数 φ(n) 为小于等于 n 且与 n 互质的正整数个数。例如 φ(1)=1， φ(8)=4。

给定正整数序列 a₁,a₂,…,a_n，请依次执行 q 个操作，操作有以下三种类型：

• 0 i x：修改 a​i​​ 的值为 x；
• 1 l r：查询 φ(a_​l​​+a​_l+1​​+⋯+a_​r​​) 的值，输出这个值对 10^​9​​+7 取模的结果；
• 2 l r：查询 φ(a_​l​​×a​_l+1​​×⋯×a_​r​​) 的值，输出这个值对 10​⁹​​+7 取模的结果。

输入格式:

输出格式:

样例输入:

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

样例输出:

8
6
36
4
6
10
144

提示:

时间限制: 1000ms
空间限制: 256MB

---