Bob Plays an exciting game known as "Product Game" In the Game, Bob has been provided an array of numbers of size \(N\) along with \(Q\)queries. For each query, he is provided with integers \(L\) and \(R\) and he has to find the product of all elements in the array between this range inclusively. Bob's task is to find the difference between the maximum and minimum solutions among all the queries.

Note:

Since the value of product can be large, print the answer modulo 1000000007.
Compute the answer to each query as \(PQ^{-1}\) modulo 1000000007, where \(Q^{-1}\) denotes the multiplicative inverse of \(Q\) modulo 1000000007
Compute overall answer modulo 1000000007.

Task:

Find the difference between the maximum and minimum solutions among all the queries.

Function Description:

Complete the function solve provided in the editor. This function takes the following two parameters and returns the required answer:

\(T:\) Test Cases

\(N: \)Size of Array

\(A:\) Array of Numbers

\(Q: \) Number of queries

\(queries: \) 2-D Array of queries containing \([L , R]\)

\(L: Lower Index\)

\(R: Upper Index \)

Input Format:

The first line contains an Integer \(T\) which is the number of the test cases.

Each Test Case will have the following :

The first line contain an integer \(N\)

the second line contains the array \(A\)

The third line contain an Integer \(Q\)

Next, Q lines contain two integers \(L \) and \(R\) in each lin

Output Format:

For each test case, print answer in a new line

Constraints

\(1\le T \le10\)

\(1 \le N \le 10^{5}\)

\(1 \le A[i] \le 10^{5}\)

\(1 \le Q \le 10^{5}\)

\(1 \le [L \le R] \le N\)