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 = (P1^A1) * (P2^A2) * .............. * (Px^Ax).

Where Pi are prime numbers and Ai 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 Ai is power of Pi.

Output:
Output the Answer Modulo 10^9 +7.

Constraints:
1 ≤ T ≤ 10
1 ≤ X ≤ 100000
0 < Pi ≤1000000
1 ≤ Ai ≤ 1000000000

SAMPLE INPUT
1
3
2 3 5
2 1 1

SAMPLE OUTPUT
90

Explanation

In given test case, The N will be 60.
So, Numbers less than and equal to 60 having same prime numbers in its factorization are 60, 30, and So, sum=90.

见题面

见题面