#P0681. 城中分支

城中分支

Description

“城市处于建设中......”
预言之子的你获得了一个拥有nn个元素的数组。
天神赋予你qq次操作:
1.1. ModifyModify,l l ,rr,xx------对于每个 i(l≤i≤r)i( l≤i≤r ),将 aia_i 乘以 xx 。
2.2. QueryQuery,l l ,rr------你需要回答φ(∏i=lrai)\varphi \left( \prod ^{r}_{i=l}a_{i}\right)取模1e9+71e9 + 7,其中φ\varphi表示欧拉函数。

正整数 nn (表示为φ(n)φ(n))的欧拉函数是满足 gcd(n,x)=1gcd(n,x)=1 的整数 x(1≤x≤n)x ( 1≤x≤n ) 的数量。
∏i=lrai\prod ^{r}_{i=l}a_{i},表示 al×al+1×.......ara_l \times a_{l+1}\times.......a_r;

Format

Input

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

第二行包含nn个整数 a1,a2,…,ana_1,a_2,…,a_n (1≤ai≤300)( 1≤a_i≤300) — 数组aa的元素。

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

Output

对于每个QueryQuery查询,打印其答案对1e9+71e9 + 7取模的结果。

Samples

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

Hint