Description

“城市处于建设中......”
预言之子的你获得了一个拥有$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 )$ 的数量。
$\prod ^{r}_{i=l}a_{i}$，表示 $a_l \times a_{l+1}\times.......a_r$;

Format

Input

第一行包含两个整数 $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$查询。

Output

对于每个$Query$查询，打印其答案对$1e9 + 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