SOLVE
LATER
It's an extremely cold day in BitLand and Vasya is in the mood to do some complex arithmetic. So, he defines the following 2 functions:
$$F(x)$$ : Largest divisor of number $$x$$ that is $$< x$$.
$$Q(A,l,r)$$: Product of $$F(x)$$ where $$l \le x \le r$$ in a certain array $$A$$
Now, Vasya has been given an array $$A$$ of size $$N$$. He needs to answer certain types of queries based on this array. In each query. he shall be given $$2$$ integers $$l$$ and $$r$$ and he needs to find $$Q(A,l,r)$$ He find this task too easy and has passed it on to you. Can you do it. As the answer to each query can be relatively large, find it Modulo $$10^9+7$$
Input Format :
The first line contains a single integers $$N$$ denoting the size of array $$A$$. The next line contains $$N$$ space separated integers denoting the elements of array $$A$$. The next line contains a single integer $$T$$ denoting the number of queries. Each of the next $$T$$ lines contain $$2$$ integers $$l$$ and $$r$$.
Output Format:
Print the answer to each query on a new line. As the answer may be large, print it Modulo $$10^9+7$$
Constraints:
$$ 1 \le N \le 10^6 $$
$$ 2 \le A[i] \le 10^7 $$
$$ 1 \le T \le 10^5 $$
$$ 1 \le l \le r \le N $$
For query $$1$$, $$F(4)$$= $$2$$, $$F(9)$$ = $$3$$. So, the answer to the query = $$2\times 3 \times3$$ = $$ 18\%(10^9+7)$$ = $$18$$
For query $$2$$, $$F(9)$$ = $$3$$ , $$F(2)$$= $$1$$. So, the answer to the query = $$3\times 3 \times1$$ = $$9\%(10^9+7)$$ = $$9$$
Challenge Name
Sapient Global Markets Core Java Hiring Challenge
Sapient Global Markets Core Java Hiring Challenge