F. Please, another Queries on Array?time limit per test5.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given an array a_1, a_2, \ldots, a_n.You need to perform q queries of the following two types:  "MULTIPLY l r x" — for every i (l \le i \le r) multiply a_i by x. "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.InputThe 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.  "MULTIPLY l r x" (1 \le l \le r \le n, 1 \le x \le 300) — denotes a multiplication query. "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.OutputFor each "TOTIENT" query, print the answer to it.ExampleInput4 45 9 1 2TOTIENT 3 3TOTIENT 3 4MULTIPLY 4 4 3TOTIENT 4 4Output112NoteIn 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.
Input4 45 9 1 2TOTIENT 3 3TOTIENT 3 4MULTIPLY 4 4 3TOTIENT 4 4
Output112
['bitmasks', 'data structures', 'divide and conquer', 'math', 'number theory', '*2400']