Please, another Queries on Array?

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

Support range multiplication and queries of Euler phi of the product of a range, modulo $10^9+7$.

Input

The first line contains $n,q$. The second line contains the array. Each of the next $q$ lines is MULTIPLY l r x or TOTIENT l r exactly as defined above.

Output

Print one answer for every TOTIENT query.

Subtasks

• Subtask 1 (20%): size and operation count at most 30; all other validity conditions are unchanged.

• Subtask 2 (30%): size and operation count at most 3000; all other validity conditions are unchanged.

• Subtask 3 (50%): full constraints:

• $1\le n\le4\cdot10^5$

• $1\le q\le2\cdot10^5$

• $1\le a_i,x\le300$

Examples

Input

4 4
5 9 1 2
TOTIENT 3 3
TOTIENT 3 4
MULTIPLY 4 4 3
TOTIENT 4 4

Output

1
1
2

Explanation

The three answers are $\varphi(1)=1$, $\varphi(2)=1$, and after multiplying the last element by 3, $\varphi(6)=2$.