#include "horses.h"
#include<bits/stdc++.h>
int mod = 1e9+7;
using namespace std;
using ll = __int128;
vector<ll>x,y,seg,segx;
set<ll>st;
ll n,loc=1,s=1;
void update(int l,int r,int u,int ind,int val){
if(l==r){
seg[u]=val;
return;
}
int mid = (l+r)/2;
if(ind<=mid) update(l,mid,u*2+1,ind,val);
else update(mid+1,r,u*2+2,ind,val);
seg[u]=(seg[u*2+1]*seg[u*2+2])%mod;
}
ll get(int l,int r,int u,int lx,int rx){
if(l>=lx && r<=rx){
return seg[u];
}
if(l>rx||r<lx){
return 1;
}
int mid = (l+r)/2;
return (get(l,mid,u*2+1,lx,rx)*get(mid+1,r,u*2+2,lx,rx))%mod;
}
void updatex(int l,int r,int u,int ind,int val){
if(l==r){
segx[u]=val;
return;
}
int mid = (l+r)/2;
if(ind<=mid) updatex(l,mid,u*2+1,ind,val);
else updatex(mid+1,r,u*2+2,ind,val);
segx[u]=max(segx[u*2+1],segx[u*2+2]);
}
ll getx(int l,int r,int u,int lx,int rx){
if(l>=lx && r<=rx){
return segx[u];
}
if(l>rx||r<lx){
return 0;
}
int mid = (l+r)/2;
return max(getx(l,mid,u*2+1,lx,rx),getx(mid+1,r,u*2+2,lx,rx));
}
ll pat(){
ll mul = 1,indd=-1,ans=1,flag=0;
auto itt = st.begin();
for(auto it = st.begin();it!=st.end();it++){
ll ind = -(*it);
mul*=x[ind];
itt=it;
if(mul>2e9) {
break;
}
}
if(itt!=st.end() && itt!=prev(st.end())) itt++;
if(mul!=1){
mul=1;
for(auto it = itt;;it--){
ll ind = -(*it);
mul*=x[ind];
ll mx = getx(0,s-1,0,ind,s-1);
if(mul*mx>ans){
ans = (mul*mx);
indd = ind;
}
if(it==st.begin())break;
if(mul>4e18) break;
}
}
if(mul<=4e9 && x[0]==1){
ll ind = 0;
//mul*=x[ind];
ll mx = getx(0,s-1,0,ind,s-1);
if(mx>ans){
ans = (mx);
indd = ind;
}
}
return (get(0,s-1,0,0,indd)*getx(0,s-1,0,indd,s-1))%mod;
}
int init(int N, int X[], int Y[]) {
n = N;
while(s<n)s*=2;
seg = segx = vector<ll>(2*s,1);
for(int i = 0;i<n;i++) {
x.push_back(X[i]);
update(0,s-1,0,i,X[i]);
if(X[i]!=1)st.insert(-i);
}
for(int i = 0;i<n;i++) y.push_back(Y[i]),updatex(0,s-1,0,i,Y[i]);
return pat();
}
int updateX(int pos, int val) {
if(x[pos]!=1) st.erase(-pos);
x[pos]=val;
if(x[pos]!=1) st.insert(-pos);
update(0,s-1,0,pos,val);
return pat();
}
int updateY(int pos, int val) {
y[pos]=val;
updatex(0,s-1,0,pos,val);
return pat();
}
