#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
int const MAX=5e5+5;
int const MOD=1e9+7;
struct node{
int prod,maxim;
};
struct AINT{
int n;
node v[4*MAX];
node combine(node a,node b){
node rasp;
rasp.prod=1LL*a.prod*b.prod%MOD;
rasp.maxim=max(a.maxim,b.maxim);
return rasp;
}
void update(int nod,int st,int dr,int pos,int val1,int val2){
if(st==dr){
if(val1>-1)
v[nod].prod=val1;
if(val2>-1)
v[nod].maxim=val2;
}
else{
int mij=(st+dr)/2;
if(pos<=mij)
update(2*nod,st,mij,pos,val1,val2);
else
update(2*nod+1,mij+1,dr,pos,val1,val2);
v[nod]=combine(v[2*nod],v[2*nod+1]);
}
}
void init(int n,int x[],int y[]){
this->n=n;
int i;
for(i=0;i<n;++i)
update(1,0,n-1,i,x[i],y[i]);
}
node query(int nod,int st,int dr,int a,int b){
if(a<=st && dr<=b)
return v[nod];
int mij=(st+dr)/2;
node ans={1,0};
if(a<=mij)
ans=combine(ans,query(2*nod,st,mij,a,b));
if(b>mij)
ans=combine(ans,query(2*nod+1,mij+1,dr,a,b));
return ans;
}
void upd(int pos,int val1,int val2){
update(1,0,n-1,pos,val1,val2);
}
node qry(int l,int r){
return query(1,0,n-1,l,r);
}
}aint;
set<int>interv;
int intv_max[MAX];
int x[MAX],y[MAX];
int n;
int get_best(){
int pos=*interv.rbegin();
long long prod=1LL*intv_max[pos]*x[pos];
auto it=interv.rbegin();
it=next(it);
while(it!=interv.rend() && prod<=1e9){
if(intv_max[*it]>prod){
pos=*it;
prod=intv_max[*it];
}
prod*=x[*it];
it=next(it);
}
return 1LL*intv_max[pos]*aint.qry(0,pos).prod%MOD;
}
int init(int N, int X[], int Y[]) {
n=N;
aint.init(N,X,Y);
int i;
interv.insert(0);
for(i=0;i<N;++i){
x[i]=X[i];
y[i]=Y[i];
if(x[i]>1)
interv.insert(i);
}
int last=N;
for(auto it=interv.rbegin();it!=interv.rend();it=next(it)){
intv_max[*it]=aint.qry(*it,last-1).maxim;
last=*it;
}
return get_best();
}
int updateX(int pos, int val) {
int old_val=x[pos];
x[pos]=val;
aint.upd(pos,val,-1);
if(pos>0){
if(old_val==1 && val>1){
interv.insert(pos);
auto it=interv.find(pos);
auto itb=prev(it);
auto itf=next(it);
intv_max[*itb]=aint.qry(*itb,*it-1).maxim;
intv_max[*it]=aint.qry(*it,(itf==interv.end())?n-1:*itf-1).maxim;
}
if(old_val>1 && val==1){
auto it=interv.find(pos);
auto itb=prev(it);
auto itf=next(it);
intv_max[*itb]=aint.qry(*itb,(itf==interv.end())?n-1:*itf-1).maxim;
interv.erase(it);
}
}
return get_best();
}
int updateY(int pos, int val) {
y[pos]=val;
aint.upd(pos,-1,val);
auto itf=interv.upper_bound(pos);
auto itb=prev(itf);
if(itf==interv.end())
intv_max[*itb]=aint.qry(*itb,n-1).maxim;
else
intv_max[*itb]=aint.qry(*itb,*itf-1).maxim;
return get_best();
}
