#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=500000+10,mod=1e9+7,lg=20,kaf=(1<<(lg));
int allx[maxn],ally[maxn],n;
set<int>st;
struct segment{
struct node{
long long maxa,zarb;
node(){
maxa=0;
zarb=1;
}
};
node seg[(1<<(lg+1))];
void upd(int i,int w){
i+=kaf;
seg[i].zarb=seg[i].maxa=w;
i>>=1;
while(i>0){
seg[i].maxa=max(seg[(i<<1)].maxa,seg[(i<<1)^1].maxa);
seg[i].zarb=seg[(i<<1)].zarb*seg[(i<<1)^1].zarb%mod;
i>>=1;
}
}
long long porszarb(int i,int l,int r,int tl,int tr){
if(l>r||l>tr||r<tl||tl>tr){
return 1;
}
if(l>=tl&&r<=tr){
return seg[i].zarb;
}
int m=(l+r)>>1;
return porszarb((i<<1),l,m,tl,tr)*porszarb((i<<1)^1,m+1,r,tl,tr)%mod;
}
long long porsmx(int i,int l,int r,int tl,int tr){
if(l>r||l>tr||r<tl||tl>tr){
return 0;
}
if(l>=tl&&r<=tr){
return seg[i].maxa;
}
int m=(l+r)>>1;
return max(porsmx((i<<1),l,m,tl,tr),porsmx((i<<1)^1,m+1,r,tl,tr));
}
}segx,segy;
int calc(){
long long low=0;
long long unnow=1;
vector<int>ind;
while((int)st.size()>0){
unnow*=allx[(*st.rbegin())];
ind.push_back((*st.rbegin()));
st.erase((*st.rbegin()));
if(unnow>1000000000){
break;
}
}
unnow/=allx[ind.back()];
long long mx=0;
for(int i=0;i<(int)ind.size();i++){
mx=max(mx,unnow*segy.porsmx(1,0,kaf-1,ind[i],n));
unnow/=allx[ind[i]];
}
mx%=mod;
mx*=segx.porszarb(1,0,kaf-1,0,ind.back());
mx%=mod;
for(auto x:ind){
st.insert(x);
}
return mx;
}
int init(int N, int X[], int Y[]) {
n=N;
allx[0]=1;
st.insert(0);
for(int i=1;i<=n;i++){
//cout<<i<<endl;
allx[i]=X[i-1];
segx.upd(i,allx[i]);
ally[i]=Y[i-1];
segy.upd(i,ally[i]);
if(allx[i]>1){
st.insert(i);
}
}
return calc();
}
int updateX(int pos, int val) {
pos++;
allx[pos]=val;
if(allx[pos]==1){
st.erase(pos);
}else{
st.insert(pos);
}
segx.upd(pos,val);
return calc();
}
int updateY(int pos, int val) {
pos++;
ally[pos]=val;
segy.upd(pos,val);
return calc();
}
