被续了大半天。。因为我不会 Miller-Rabin，更不会Pollard-Rho，而且作为一个自带大常数的菜鸡，我写的Pollard-Rho甚至过不去洛谷上的模板QAQ（因为没写路径倍增？）
言归正传，假设我们有充足的时间枚举每一个 (x)，那么在 (x) 确定的情况下，原式变成了一个模方程。
根据裴蜀定理，我们知道只有当 (gcd(x,P)|Q) 的情况下方程有 (gcd(x,P)) 个解。
枚举一下gcd，再乱推一气，就可以得到$$ ans=sum_{d|P,d|Q} d cdot varphi (frac{P}{d} )$$
然后我就不会搞了QAQ，翻翻题解，发现这是一个积性函数(ΩДΩ)
那我们就可以算出每个质因子的贡献再乘起来。
对于一个质因子 (x) ，假设 (P) 里有 (p) 个，(Q) 里有 (q) 个，那它对答案的贡献就是
[sum_x=sum_{i=0}^{min(p,q)} x^i cdot varphi(x^{p-i})
]
把 (varphi) 拆掉，就变成了
[sum_x=x^{p-1} cdot (x-1) cdot (min(p,q)+1)
]
但是要判下 (p=i) 的情况，因为这时候 (varphi(1)=1)，不满足 (varphi(x^{p-1})=(x-1) cdot x^{p-i-1})
用Pollard-Rho分解质因数后，就可以算了^(#｀∀´)_Ψ（其实这个颜文字，原本后面的字是“打架吗”）
由于这题范围很大，还要用龟速乘= =（话说我不会快速乘啊 (っ°Д°;)っ）
玄学的是，我一开始T了，搞来数据发现，我本机明明飞快啊？然后#define rand() rand()%10000就过了。。大概是win和linux的rand()范围不太一样？更玄学的是，BZOJ上手动吸氧吸臭氧怎么更慢了= =
为什么每次我的题解都有一堆废话，然后在关键部分一带而过
#include<bits/stdc++.h>
#define LL long long
#define rand() rand()%10000
#define fr(i,x,y) for(int i=(x);i<=(y);i++)
#define rf(i,x,y) for(int i=(x);i>=(y);i--)
#define frl(i,x,y) for(int i=(x);i<(y);i++)
using namespace std;
const int N=12;
const int MOD=1e9+7;
const int RP=5;
int n;
void read(int &x){
char ch=getchar();x=0;
for(;ch<'0'||ch>'9';ch=getchar());
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
}
void read(LL &x){
char ch=getchar();x=0;
for(;ch<'0'||ch>'9';ch=getchar());
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
}
LL gcd(LL a,LL b){
return b==0?a:gcd(b,a%b);
}
inline void Add(int &x,int y,int p){
x+=y;
while(x<0) x+=p;
while(x>=p) x-=p;
}
inline void Add(LL &x,LL y,LL p){
x+=y;
while(x<0) x+=p;
while(x>=p) x-=p;
}
inline LL qmul(LL a,LL n,LL p){
LL ans=0;
for(LL sum=a;n;n>>=1,Add(sum,sum,p)) if (n&1) Add(ans,sum,p);
return ans;
}
inline LL qpow(LL a,LL n,LL p){
LL ans=1;
for(LL sum=a;n;n>>=1,sum=qmul(sum,sum,p)) if (n&1) ans=qmul(ans,sum,p);
return ans;
}
int MRPD(LL n,int rp){
if (n==2||n==3||n==7) return 1;
if (n<=1||n%2==0||n%3==0||n%7==0) return 0;
while(rp--){
LL a=1LL*rand()%(n-2)+2;
LL x=n-1,v=qpow(a,x,n);
if (v!=1) return 0;
while(!(x&1)){
x>>=1;v=qpow(a,x,n);
if (v!=1&&v!=n-1) return 0;
if (v==n-1) break;
}
}
return 1;
}
map<LL,int> mp1,mp2;
inline LL f(LL x,LL c,LL n){
LL ans=qmul(x,x,n);Add(ans,c,n);
return ans;
}
void PRRP(LL n,map<LL,int> &mp){
while(!(n&1)) n>>=1,mp[2]++;
if (n==1) return;
if (MRPD(n,RP)) return mp[n]++,void();
LL c=rand(),p1=rand(),p2=f(p1,c,n),g;
while((g=gcd(abs(p1-p2),n))==1){
p1=f(p1,c,n);
p2=f(f(p2,c,n),c,n);
if (p1==p2) return PRRP(n,mp),void();
}
PRRP(g,mp);PRRP(n/g,mp);
}
LL a[N],b[N];
int main(){
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
srand(19260817);
read(n);
fr(i,1,n){
read(a[i]);
PRRP(a[i],mp1);
}
fr(i,1,n){
read(b[i]);
if (!b[i]){
fr(i,1,n) b[i]=a[i];
break;
}
}
fr(i,1,n) PRRP(b[i],mp2);
LL ans=1;
for(map<LL,int>::iterator it=mp1.begin();it!=mp1.end();it++){
LL x=it->first;int p=it->second,q=mp2[x];LL sum=0;
x%=MOD;
LL ps=min(p,q);Add(sum,qpow(x,p-1,MOD)*(x-1)%MOD*(ps)%MOD,MOD);
if (p<=ps) Add(sum,qpow(x,p,MOD),MOD);
else Add(sum,qpow(x,p-1,MOD)*(x-1)%MOD,MOD);
ans=ans*sum%MOD;
}
cout<<ans<<endl;
return 0;
}