Vasya and Mathematical Analysis
Tag(s):

## Easy-Medium, Math, Number Theory, Sieve

Problem
Editorial
Analytics

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$

SAMPLE INPUT
4
4 9 9 2
2
1 3
2 4
SAMPLE OUTPUT
18
9
Explanation

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

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

Sapient Global Markets Core Java Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Basic Math
• Math > Number Theory