Lại thêm truy vấn trên mảng (Please, another Queries on Array?)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Mảng $a_i$. MULTIPLY l r x nhân mọi phần tử đoạn với $x$. TOTIENT l r yêu cầu $\varphi(\prod_{i=l}^{r}a_i)$ modulo $10^9+7$.

Input

Dòng đầu chứa $n,q$. Dòng thứ hai chứa $a_1,a_2,\ldots,a_n$. Mỗi trong $q$ dòng tiếp theo là:

• MULTIPLY l r x: nhân mọi $a_i$ với $x$ cho $l\le i\le r$.
• TOTIENT l r: hỏi $\varphi(\prod_{i=l}^{r}a_i)$ modulo $10^9+7$.

Output

Mỗi truy vấn TOTIENT in một đáp án.

Subtask

• Subtask 1 (20%): $n$ và số thao tác không vượt 30; các điều kiện còn lại giữ như đề đầy đủ.

• Subtask 2 (30%): $n$ và số thao tác không vượt 3000; các điều kiện còn lại giữ như đề đầy đủ.

• Subtask 3 (50%): toàn bộ giới hạn:

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

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

• $1\le a_i,x\le300$

Ví dụ

Input

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

Output

1
1
2

Giải thích

Ba truy vấn lần lượt là $\varphi(1)=1$, $\varphi(2)=1$ và sau khi nhân phần tử cuối với 3 thì $\varphi(6)=2$.