Please, another Queries on Array?
Contest: Codeforces Round 538 (Div. 2)
Difficulty rating: 2400
Tags: bitmasks, data structures, divide and conquer, math, number theory

You are given an array $$$a_1, a_2, \ldots, a_n$$$.

You need to perform $$$q$$$ queries of the following two types:

1. "MULTIPLY l r x" — for every $$$i$$$ ($$$l \le i \le r$$$) multiply $$$a_i$$$ by $$$x$$$.
2. "TOTIENT l r" — print $$$\varphi(\prod \limits_{i=l}^{r} a_i)$$$ taken modulo $$$10^9+7$$$, where $$$\varphi$$$ denotes Euler's totient function.

The Euler's totient function of a positive integer $$$n$$$ (denoted as $$$\varphi(n)$$$) is the number of integers $$$x$$$ ($$$1 \le x \le n$$$) such that $$$\gcd(n,x) = 1$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n \le 4 \cdot 10^5$$$, $$$1 \le q \le 2 \cdot 10^5$$$) — the number of elements in array $$$a$$$ and the number of queries.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 300$$$) — the elements of array $$$a$$$.

Then $$$q$$$ lines follow, describing queries in the format given in the statement.

1. "MULTIPLY l r x" ($$$1 \le l \le r \le n$$$, $$$1 \le x \le 300$$$) — denotes a multiplication query.
2. "TOTIENT l r" ($$$1 \le l \le r \le n$$$) — denotes a query on the value of Euler's totient function.

It is guaranteed that there is at least one "TOTIENT" query.

Output format:
For each "TOTIENT" query, print the answer to it.

Constraints:
Time limit: 5.5 s
Memory limit: 256.0 MB

Note:
In the first example, $$$\varphi(1) = 1$$$ for the first query, $$$\varphi(2) = 1$$$ for the second query and $$$\varphi(6) = 2$$$ for the third one.

Example input:
4 4
5 9 1 2
TOTIENT 3 3
TOTIENT 3 4
MULTIPLY 4 4 3
TOTIENT 4 4

Example output:
1
1
2

Editorial:
There's a few fundamentals about Euler's totient we need to know:
• $$$\varphi(p) = p-1$$$ and $$$\varphi(p^k) = p^{k-1} \cdot (p - 1)$$$, provided $$$p$$$ is a prime number and $$$k$$$ is a positive integer. You can easily prove these equations through the definition of the function itself.
• Euler's totient is a multiplicative function. $$$f(x)$$$ is considered a multiplicative function when $$$\gcd(a, b) = 1$$$ means $$$f(a) \cdot f(b) = f(a \cdot b)$$$.
Keep in mind that we can rewrite $$$\varphi(p^k)$$$ as of following: $$$\varphi(p^k) = p^k \cdot \frac{p-1}{p}$$$.
Let's denote $$$P$$$ as the set of prime factors of $$$\prod \limits_{i=l}^{r} a_i$$$.
Thus, the answer for each query will simply be: $$$\varphi(\prod \limits_{i=l}^{r} a_i) = \prod \limits_{i=l}^{r} a_i \cdot \prod \limits_{p \in P} \frac{p-1}{p}$$$.
So, for each query we'll need to know the product of the elements, and which primes are included in that product.
There are a few ways to work around with it. One of the most effective way is as following:
• Create a product segment tree to maintain the segment products.
• Since $$$\prod \limits_{p \in P} \frac{p-1}{p}$$$ only depends on the appearance or non-appearance of the primes, and the constraints guaranteed us to have at most $$$62$$$ prime factors, we can use bitmasks and an or-sum segment tree to maintain this part.
Complexity for initializing segment trees: $$$\mathcal{O}\left( n \cdot \log(n) \right)$$$.
Complexity for each update query: $$$\mathcal{O}\left( 62 + \log^2(n) \right)$$$.
Complexity for each return query: $$$\mathcal{O}\left( 62 + \log^2(n) \right)$$$.