#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
#define y1 da
#define y2 ne
#define ll long long
const ll MAXN=5e6+6;
const ll MOD=1e9+7;
ll x1[MAXN],y1[MAXN];
ll fastpow(ll x,ll p)
{
if(p==0)return 1;
if(p==1)return x;
//if(p==2)return (x*x)%MOD;
ll t=fastpow(x,p/2);
t*=t;t%=MOD;
if(p%2==1)t*=x;
t%=MOD;
return t;
}
ll inverse(ll x)
{
return fastpow(x,MOD-2);
}
set<ll>notones;
ll treeX[4*MAXN],treeY[4*MAXN];
void updateY(ll idx,ll l,ll r,ll q,ll val)
{
if(l>q||r<q)return;
if(l==r)
{
treeY[idx]=val;
return;
}
ll mid=(l+r)/2;
if(mid>=q)updateY(idx*2,l,mid,q,val);
else updateY(idx*2+1,mid+1,r,q,val);
treeY[idx]=max(treeY[idx*2],treeY[idx*2+1]);
}
ll n;
ll queryY(ll idx,ll l,ll r,ll ql,ll qr)
{
if(l>qr)return 0;
if(r<ql)return 0;
if(l>=ql&&r<=qr)return treeY[idx];
ll mid=(l+r)/2;
if(mid+1>qr)return queryY(idx*2,l,mid,ql,qr);
if(mid<ql)return queryY(idx*2+1,mid+1,r,ql,qr);
return max(queryY(idx*2,l,mid,ql,qr),queryY(idx*2+1,mid+1,r,ql,qr));
}
void updateX(ll idx,ll l,ll r,ll q,ll val)
{
if(l>q||r<q)return;
if(l==r)
{
treeX[idx]=val;
return;
}
ll mid=(l+r)/2;
if(mid>=q)updateX(idx*2,l,mid,q,val);
else updateX(idx*2+1,mid+1,r,q,val);
treeX[idx]=((ll)treeX[idx*2]*treeX[idx*2+1])%MOD;
}
ll queryX(ll idx,ll l,ll r,ll ql,ll qr)
{
if(l>qr)return 1;
if(r<ql)return 1;
if(l>=ql&&r<=qr)return treeX[idx];
ll mid=(l+r)/2;
if(mid+1>qr)return queryX(idx*2,l,mid,ql,qr);
if(mid<ql)return queryX(idx*2+1,mid+1,r,ql,qr);
return ((ll)queryX(idx*2,l,mid,ql,qr)*queryX(idx*2+1,mid+1,r,ql,qr))%MOD;
}
ll prodall=1;
ll solve()
{
if(notones.size()==0)
{
return queryY(1,0,n-1,0,n-1);
}
ll last=n;
auto it=notones.end();--it;
ll d1=1;
pair<ll,ll>ans;
ans={-1,-1};
ll y2,cnt=0;
for(;;--it)
{
cnt++;
ll y1=queryY(1,0,n-1,(*it),last-1);
if(ans.first==-1)
{
y2=y1;
ans.first=y1;
ans.second=d1;
}
else if(ans.first*d1<y1*ans.second)
{
ans.first=y1;y2=y1;
ans.second=d1;
}
//if(cnt>100)break;
if(it==notones.begin())break;
last=(*it);d1=(ll)d1*x1[(*it)];
if(d1>(ll)1e9)break;
if(d1>(ll)1e9*ans.second/ans.first)break;
}
/*it=notones.end();--it;
last=n;
for(;;--it)
{
--j;
if(j==0)
{
//cout<<queryX(1,0,n-1,0,(*it))<<" "<<queryY(1,0,n-1,(*it),last-1)<<endl;
return ((ll)queryX(1,0,n-1,0,(*it))*queryY(1,0,n-1,(*it),last-1))%MOD;
}
last=(*it);
}*/
ll f=prodall;
f*=inverse(ans.second);
f%=MOD;
ll t=(f*y2)%MOD;
ll g=queryY(1,0,n-1,0,n-1);
return max(g,t);
return (f*y2)%MOD;
return 0;
}
int init(int N, int X[], int Y[]) {
n=N;
for(ll i=0;i<N;++i)
{
x1[i]=X[i];
y1[i]=Y[i];
prodall*=x1[i];prodall%=MOD;
if(X[i]>1)
{
notones.insert(i);
}
//updateX(1,0,N-1,i,X[i]);
}
for(ll i=0;i<N;++i)
{
updateY(1,0,N-1,i,Y[i]);
}
return solve();
}
int updateX(int pos, int val) {
prodall*=inverse(x1[pos]);prodall%=MOD;
x1[pos]=val;
prodall*=x1[pos];prodall%=MOD;
if(val==1)
{
notones.erase(pos);
}
else notones.insert(pos);
//updateX(1,0,n-1,pos,x1[pos]);
return solve();
}
int updateY(int pos, int val) {
y1[pos]=val;
updateY(1,0,n-1,pos,y1[pos]);
return solve();
}
