Link: https://ac.nowcoder.com/acm/contest/9984/J
Source: niuke.com

As we all know, Wu Chengyao is learning Euclidean algorithm.

Now she can easily solve gcd(x1,..., xn) and is proud of it. In order to punish the arrogant Wu Chengyao, her roommate gave him the formula of $GCD (x {1} {p 1},..., X {n} {P _n}) $.

Wu Chengyao was baffled and had to come to you for help. I hope you can help her find this formula.
Since the result may be very large, you need to take the model of 1e9+7.
In particular, Wu Chengyao's roommate thinks gcd ⁡ (x)=x.

Enter Description:

The first line is represented by a number n . 

Second line n Number, No i Number representation xixi . 

Third line n Number, No i Number representation pipi . 

Of which, 1≤n,xi,pi≤1e41≤n,xi,pi≤1e4 . 

Output Description:

Output a line and a number to represent the answer.

Example 1

input

copy

2
9 3
1 2

output

copy

9

Direct violence is clearly undesirable. Considering the nature of gcd:

Let \ (a=p_1^{a1}p_2^{a2}p_3^{a3}... b = p_1^{b1}p_2^{b2}p_3^{b3} \), the associative unique decomposition theorem, then \ (gcd(a, b) = p_1^{min(a1,b1)}p_2^{min(a2,b2)}p_3^{min(a3,b3)}...\)

gcd extended to multiple numbers is also true. For this problem, gcd of multiple powers is required. In fact, it only needs to multiply the exponent of prime number by the last power when taking min. For example, let \ (a=p_1^{a1}p_2^{a2}p_3^{a3}... b = p_1^{b1}p_2^{b2}p_3^{b3} \) associate the unique decomposition theorem, then \ (gcd(a^s, b^t) = p_1^{min(a1\times s,b1\times t)}p_2^{min(a2\times s,b2\times t)}p_3^{min(a3\times s,b3\times t)}...\)

It is observed that the range of numbers is 1e4, so open an array factor, and factor[i] represents the power of the prime number I (if it is a prime number, it is not the power of the prime number. Naturally, it has no effect) (in gcd). For each to pi c, the prime number of [i] [i] [PP factor] is first updated according to the decomposition of [i] [PP factor], i.e. [i] [min]; CC [i] is the number of times of the current prime number obtained after x decomposition, and np is the original number of times of x. Of course, if the current factor[i] is 0, it will be assigned directly. Instead of 0, take min. Finally, calculate gcd with fast power: \ (gcd = \ Sigma {I = 1} ^ {10000} I ^ {factor[i]} \).

But there will be problems if you write this directly: for example, the decomposed prime factor of an X does not contain 5, and factor[5] has been updated to a non-zero number when traversing other X. at this time, factor[5] should be set to 0 according to the above formula, but if you have to judge all prime numbers in the range for each x, it will obviously explode. Therefore, we can open another cnt array. cnt[i] represents the number of X in which all the prime factors of X contain the prime number I (if it is a prime number). factor[i] is not 0, if and only if cnt[i] == n (i.e. the total number of x input), judge when traversing the calculation at last. The complexity is \ (n\sqrt{n} \).

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define mod 1000000007
using namespace std;
long long x[10005], p[10005];
int n;
long long fpow(long long aa, long long bb)
{
	long long ans = 1;
	for(; bb; bb >>= 1)
	{
		if(bb & 1) ans = ans * aa % mod;
		aa = aa * aa % mod;
	}
	return ans;
}
long long pp[10005], cc[10005];//Unique decomposition theorem board, pp stores the prime number decomposed, and cc stores the corresponding power
int m = 0;
long long factor[10005], cnt[10005];
void divide(long long nn, long long np)
{
	m = 0;
	for(long long i = 2; i <= sqrt(nn); i++)
	{
		if(nn % i == 0)
		{
			pp[++m] = i, cc[m] = 0;
			while(nn % i == 0) nn /= i, cc[m]++;
		}
	}
	if(nn > 1) pp[++m] = nn, cc[m] = 1;
	for(int i = 1; i <= m; i++)//Update the factor array after decomposition
	{
		if(factor[pp[i]]) factor[pp[i]] = min(factor[pp[i]], cc[i] * np);
		else factor[pp[i]] = cc[i] * np;
		cnt[pp[i]]++;
	}
}
int main()
{
	freopen("data.txt", "r", stdin);
	memset(factor, 0, sizeof(factor));
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> x[i];
	for(int i = 1; i <= n; i++) cin >> p[i];
	for(int i = 1; i <= n; i++) divide(x[i], p[i]);
	long long ans = 1;
	for(int i = 2; i <= 10000; i++)
		if(cnt[i] == n) 
			ans = ans * fpow(i, factor[i]) % mod;
	cout << ans;
	return 0;
}