John loves prime numbers. One day he was playing a game "primcia" with his wife alicia. The game is as follows, John write a number N on a table.

The number is of the form:

N = (P₁^A₁) * (P₂^A₂) * .............. * (P_x^A_x).

Where P_i are prime numbers and A_i are its corresponding powers.

Now, he asks Alicia to find the sum of all the numbers which are less than or equal to N and also contain all prime numbers which N contains in its prime factorization. For small numbers, Alicia can solve easily but it becomes too hard for large numbers. Help her to answer the query of john.

Input:
First Line contains T test cases. Each test case contains 3 lines, 1st line contain X numbers of primes in N, 2nd line contains X distinct prime numbers and 3rd line contain X powers. Each power A_i is power of P_i.

Output:
Output the Answer Modulo 10⁹ +7.

Constraints:
1 <= T <= 10
1 <= X <= 100000
0 < P_i <=1000000
1<= A_i <= 1000000000

Please login to use the editor

Loading...