城中分支
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

“城市处于建设中......”
预言之子的你获得了一个拥有n个元素的数组。
天神赋予你q次操作：
1. Modify，l，r，x------对于每个 i( l≤i≤r )，将 a_i 乘以 x 。
2. Query，l，r------你需要回答\varphi \left( \prod ^{r}_{i=l}a_{i}\right)取模1e9 + 7，其中\varphi表示欧拉函数。

正整数 n (表示为φ(n))的欧拉函数是满足 gcd(n,x)=1 的整数 x ( 1≤x≤n ) 的数量。
\begin{aligned}\prod ^{r}a_{i}\\ i=l\end{aligned} 表示a_l \times a_{l+1}\times.....a_r

输入描述:

第一行包含两个整数 n 和 q(1≤n≤4⋅10^5,1≤q≤2⋅10^5) — 数组中的元素数和查询数。

第二行包含n个整数 a_1,a_2,…,a_n ( 1≤a_i≤300) — 数组a的元素。

接下来是q行以语句中给出的格式描述查询。
Modify，l，r，x ( 1≤l≤r≤n, 1≤x≤300 ) —表示修改操作。
Query，l，r ( 1≤l≤r≤n) ——表示对欧拉函数值的查询操作。
数据保证至少有一个Query查询。

输出描述:

对于每个Query查询，打印其答案对1e9 + 7取模的结果。
示例1

输入

复制 
4 4
5 9 1 2
Query 3 3
Query 3 4
Modify 4 4 3
Query 4 4

输出

复制 
1
1
2
示例2

输入

复制 
1 1
4
Query 1 1

输出

复制 
2