#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<ctime>

#define ll long long

using namespace std;

const int N=,mod=1e9+;

int n,ans=,c[N],c2[N],tot;

ll p[N],P=;

bool vis[N],flag;

ll rdl()

{

  ll ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='') ret=(ret<<3ll)+(ret<<1ll)+ch-'',ch=getchar();

  return fx?ret:-ret;

}

void upd(ll &x,ll md){x-=(x>=md?md:);}

ll mul(ll a,ll b,ll md)

{

  ll ret=;//0!

  while(b)

    {

      if(b&1ll)ret=ret+a,upd(ret,md);

      a=a+a,upd(a,md);b>>=1ll;

    }

  return ret;

}

ll pw(ll x,ll k,ll md)

{

  ll ret=;

  while(k)

    {

      if(k&1ll)ret=mul(ret,x,md);

      x=mul(x,x,md);k>>=1ll;

    }

  return ret;

}

int phi(ll p,int k)

{

  if(!k) return ;

  return mul(p-,pw(p,k-,mod),mod);

}

void add(ll a,bool flag)

{

  if(flag)

    {

      for(int i=;i<=tot;i++)

    if(p[i]==a)

      { c[i]++;return;}

      p[++tot]=a; c[tot]=;

    }

  else

    {

      for(int i=;i<=tot;i++)

    if(p[i]==a&&c2[i]<c[i])

      c2[i]++;//Q=gcd()

    }

}

bool ml_rb(ll n)

{

  if(n<)return false;if(n==)return true;if((n&)==)return false;

  ll u=n-,t=;

  while((u&)==){u>>=,t++;}

  int s=;

  while(s--)

    {

      ll a=rand()%(n-)+;//2~n-1

      a=pw(a,u,n); ll pre=a;

      for(int i=;i<=t;i++)

    {

      a=mul(a,a,n);

      if(a==&&pre!=&&pre!=n-)return false;

      pre=a;

    }

      if(a!=) return false;

    }

  return true;

}

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

ll pl_rho(ll x,ll c)

{

  ll x0=rand()%x,y0=x, k=,i=;

  while()

    {

      x0=(mul(x0,x0,x)+c)%x;

      ll g=gcd(abs(x0-y0),x);

      if(g!=&&g!=x) return g;

      if(x0==y0)return x;

      if((++i)==k){k<<=;y0=x0;}

    }

}

void fd_fac(ll n,bool flag)

{

  if(n<)return;

  if(ml_rb(n))

    {

      add(n,flag);return;

    }

  ll p=n;

  while(p==n)p=pl_rho(p,rand()%(n-)+);

  fd_fac(p,flag); fd_fac(n/p,flag);

}

int main()

{

  srand(time());  n=rdl();

  for(int i=;i<=n;i++)

    {

      ll a=rdl(); P=mul(P,a,mod);

      fd_fac(a,);

    }

  for(int i=;i<=n;i++)

    {

      ll a=rdl(); if(!a){flag=;continue;}

      if(flag)continue;

      fd_fac(a,);

    }

  if(flag)for(int i=;i<=tot;i++)c2[i]=c[i];

  for(int i=,d,tp;i<=tot;i++)

    {

      tp=pw(p[i],c[i]-,mod);

      d=mul(tp,mul(p[i]-,c2[i]+,mod)+(c[i]==c2[i]),mod);

      ans=mul(ans,d,mod);

    }

  printf("%d\n",ans);

  return ;

}