给你一个数组 $$$a_1, a_2, \ldots, a_n$$$。
您需要执行以下两种类型的 $$$q$$$ 查询:
1.“乘 l r x”— 对于每个 $$$i$$$ ($$$l \le i \le r$$$) 将 $$$a_i$$$ 乘以 $$$x$$$。
2. "TOTIENT l r" — print $$$\varphi(\prod \limits_{i=l}^{r} a_i)$$$ 对 $$$10^9+7$$$ 取模,其中 $$$\varphi$$$ 表示欧拉 totient 函数。
正整数 $$$n$$$ 的欧拉 totient 函数(表示为 $$$\varphi(n)$$$)是满足 $$$\gcd(n,x) = 1$$$ 的整数 $$$x$$$ ($$$1 \le x \le n$$$) 的数量。
输入
第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n \le 4 \cdot 10^5$$$, $$$1 \le q \le 2 \cdot 10^5$$$) - 数组 $$$a$$$ 中的元素数量和查询数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 300$$$) — 数组 $$$a$$$ 的元素。
接下来是 $$$q$$$ 行,以语句中给出的格式描述查询。
1. "MULTIPLY l r x" ($$$1 \le l \le r \le n$$$, $$$1 \le x \le 300$$$) — 表示乘法查询。
2. "TOTIENT l r" ($$$1 \le l \le r \le n$$$) — 表示查询欧拉 totient 函数的值。
保证至少有一个“TOTIENT”查询。
输出
对于每个“TOTIENT”查询,打印其答案。
示例
输入 #1
4 4 5 9 1 2 TOTIENT 3 3 TOTIENT 3 4 MULTIPLY 4 4 3 TOTIENT 4 4
输出 #1
1 1 2
注意
在第一个示例中,第一个查询的 $$$\varphi(1) = 1$$$,第二个查询的 $$$\varphi(2) = 1$$$,第三个查询的 $$$\varphi(6) = 2$$$。