Problem: 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.

Solution (in PYTHON):

Solution:
M=10**9+7
for i in range(input()):
	a=input()
	l=[int(x) for x in raw_input().split()]
	l1=[int(y) for y in raw_input().split()]
	n = 1
	for j in range(0,len(l1)):
		n *= ((pow(l[j],l1[j]+1,M)-l[j]+M)%M)*(pow(l[j]-1,M-2,M))
		n %= M
	print n