E. RADiant queries
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Let rad$$$(n)$$$ denote the product of all distinct prime divisors of the number $$$n$$$. For example, rad$$$(504)$$$ = rad$$$(2^3 \cdot 3^2 \cdot 7)$$$ $$$= 2 \cdot 3 \cdot 7$$$ $$$=42$$$. We define rad$$$(1) = 1$$$.

The statement of this problem is simple: you have an array $$$a$$$ of size $$$n$$$. You are given $$$q$$$ queries $$$[\ell;r]$$$, and you need to compute rad of the product of the numbers $$$a_\ell, a_{\ell + 1}, \dots, a_r$$$, that is: $$$$$$\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)$$$$$$ Since this number can be quite large, output it modulo $$$10^9 + 7$$$.

Input

The first line of input contains two numbers $$$n,q$$$ ($$$1 \le n,q \le 5 \cdot 10^5$$$), the number of elements in the array and the number of queries.

The second line of input contains $$$n$$$ numbers $$$a_i$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$), the array $$$a$$$.

In the following $$$q$$$ lines, two numbers $$$\ell, r$$$ ($$$1 \le \ell \le r \le n$$$) are given, which are the boundaries of the next query.

Output

In $$$q$$$ lines of output, print one number per line, the answer to the problem modulo $$$10^9 + 7$$$.

Scoring
№Additional ConstraintsPointsReq. GroupsComment
$$$n$$$$$$q$$$$$$a_i$$$
$$$0$$$—————Tests from the statement
$$$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$$$—All $$$a_i$$$ are prime and distinct
$$$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$$$All $$$a_i$$$ are prime
$$$13$$$———$$$12$$$$$$0-12$$$—
Examples
Input
5 6
42 35 11 26 13
1 3
2 4
3 5
1 5
2 2
4 5
Output
2310
10010
286
30030
35
26
Input
2 1
2 2
1 2
Output
2