beautiful-primes

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.

Source: hackerearth | Difficulty: MEDIUM
Tags: Mathematics


Solutions:
M = 10**9 + 7
for t in range(eval(input())):
	X = eval(input())
	P = list(map(int,input().split()))
	A = list(map(int,input().split()))
	
	res = 1
	for i in range(len(A)):
		res *= ((pow(P[i],A[i]+1,M)-P[i]+M)%M)*(pow(P[i]-1,M-2,M))
		res %= M
	print(res)