F. Очередная задача про запросы к массиву
ограничение по времени на тест
5.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a_1, a_2, \ldots, a_n$$$.

Необходимо выполнить $$$q$$$ запросов следующих двух видов:

  1. «MULTIPLY l r x» — для каждого $$$i$$$ ($$$l \le i \le r$$$) нужно умножить $$$a_i$$$ на $$$x$$$.
  2. «TOTIENT l r» — вычислить $$$\varphi(\prod \limits_{i=l}^{r} a_i)$$$ по модулю $$$10^9+7$$$, где $$$\varphi$$$ обозначает функцию Эйлера.

Функцией Эйлера целого положительного числа $$$n$$$ (обозначается как $$$\varphi(n)$$$) называется количество целых чисел $$$x$$$ ($$$1 \le x \le n$$$), таких что $$$\gcd(n,x) = 1$$$.

Входные данные

Первая строка содержит два целых числа $$$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» выведите ответ на него.

Пример
Входные данные
4 4
5 9 1 2
TOTIENT 3 3
TOTIENT 3 4
MULTIPLY 4 4 3
TOTIENT 4 4
Выходные данные
1
1
2
Примечание

В первом примере $$$\varphi(1) = 1$$$ для первого запроса, $$$\varphi(2) = 1$$$ для второго запроса и $$$\varphi(6) = 2$$$ для третьего.