Beautiful primes
Approved
Math
Medium
Open
45.0% success
3,772 attempts
2s time
256MB memory
1024KB max code

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 = (P1A1) * (P2A2) * .............. * (PxAx).

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 109 +7.

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

Examples
Input
1
3
2 3 5
2 1 1
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.

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading Editor...