E. РАДодододостные запросы
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Обозначим за rad$$$(n)$$$ произведение всех различных простых делителей числа $$$n$$$. Например, rad$$$(504)$$$ = rad$$$(2^3 \cdot 3^2 \cdot 7)$$$ $$$= 2 \cdot 3 \cdot 7$$$ $$$=42$$$. Положим rad$$$(1) = 1$$$.

Условие этой задачи просто: у вас есть массив $$$a$$$ размера $$$n$$$. Вам дано $$$q$$$ запросов $$$[\ell;r]$$$, посчитать rad произведения чисел $$$a_\ell, a_{\ell + 1}, \dots, a_r$$$, то есть: $$$$$$\displaystyle\texttt{rad}\left(\prod_{i=\ell}^{r} a_i\right) = \texttt{rad}\left(a_\ell \times a_{\ell + 1} \times \dots \times a_r \right)$$$$$$ Так как это число может быть довольно большим, выведите его по модулю $$$10^9 + 7$$$.

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

В первой строке входных данных вводятся два числа $$$n,q$$$ ($$$1 \le n,q \le 5 \cdot 10^5$$$), количество элементов в массиве и количество запросов.

Во второй строке входных данных вводится $$$n$$$ чисел $$$a_i$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$), массив $$$a$$$.

В следующих $$$q$$$ строках вводится по два числа $$$\ell, r$$$ ($$$1 \le \ell \le r \le n$$$), границы очередного запроса.

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

В $$$q$$$ строках выходных данных выведите по одному числу, ответ на задачу по модулю $$$10^9 + 7$$$.

Система оценки
№Доп. ограниченияБаллыНеобх. группыКомментарий
$$$n$$$$$$q$$$$$$a_i$$$
$$$0$$$—————Тесты из условия
$$$1$$$$$$n \le 100$$$$$$q \le 100$$$$$$a_i \le 100$$$$$$8$$$$$$0$$$—
$$$2$$$—$$$9$$$$$$1$$$—
$$$3$$$$$$n \le 1000$$$$$$q \le 1000$$$$$$a_i \le 1000$$$$$$10$$$$$$1$$$—
$$$4$$$—$$$11$$$$$$1-3$$$—
$$$5$$$———$$$11$$$—Все $$$a_i$$$ простые и различные
$$$6$$$——$$$a_i \le 300$$$$$$12$$$$$$0-2$$$—
$$$7$$$$$$n \le 5 \cdot 10^4$$$$$$q \le 5 \cdot 10^4$$$—$$$7$$$$$$0,1,3$$$—
$$$8$$$$$$n \le 10^5$$$$$$q \le 10^5$$$—$$$4$$$$$$7$$$—
$$$9$$$$$$n \le 2 \cdot 10^5$$$$$$q \le 2 \cdot 10^5$$$—$$$4$$$$$$8$$$—
$$$10$$$$$$n \le 3 \cdot 10^5$$$$$$q \le 3 \cdot 10^5$$$—$$$3$$$$$$9$$$—
$$$11$$$$$$n \le 4 \cdot 10^5$$$$$$q \le 4 \cdot 10^5$$$—$$$2$$$$$$10$$$—
$$$12$$$———$$$7$$$$$$5$$$Все $$$a_i$$$ простые
$$$13$$$———$$$12$$$$$$0-12$$$—
Примеры
Входные данные
5 6
42 35 11 26 13
1 3
2 4
3 5
1 5
2 2
4 5
Выходные данные
2310
10010
286
30030
35
26
Входные данные
2 1
2 2
1 2
Выходные данные
2