#pragma once
#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7, MAXN=500005;
long long a[MAXN], b[MAXN];
int n;
struct Node{
long long prod, rmq;
};
Node st[2<<20];
set<long long> h;
void build(int v, int s, int e){
if(s==e){
st[v].prod=a[s];
st[v].rmq=b[s];
return;
}
int m=(s+e)/2;
build(v*2, s, m);
build(v*2+1, m+1, e);
st[v].prod=(st[v*2].prod*st[v*2+1].prod)%mod;
st[v].rmq=max(st[v*2].rmq, st[v*2+1].rmq);
return;
}
void upd(int v, int s, int e, const int ts, const int te, Node xx){
if(e<ts||s>te){
return;
}else if(ts<=s&&e<=te){
if(xx.rmq==-1){
st[v].prod=xx.prod;
}else st[v].rmq=xx.rmq;
return;
}
int m=(s+e)/2;
upd(v*2, s, m, ts, te, xx);
upd(v*2+1, m+1, e, ts, te, xx);
st[v].prod=(st[v*2].prod*st[v*2+1].prod)%mod;
st[v].rmq=max(st[v*2].rmq, st[v*2+1].rmq);
}
long long que(int v, int s, int e, const int ts, const int te, bool type){
if(e<ts||s>te){
if(type==0){
return 1;
}else return 0;
}else if(ts<=s&&e<=te){
if(type==0){
return st[v].prod%mod;
}else return st[v].rmq;
}
int m=(s+e)/2;
if(type==0){
return (que(v*2, s, m, ts, te, type)*que(v*2+1, m+1, e, ts, te, type))%mod;
}else return max(que(v*2, s, m, ts, te, type), que(v*2+1, m+1, e, ts, te, type));
}
int calc(){
int j, count=0;
long long prod=1, last_y;
vector<int> indices;
for(auto it=h.rbegin(); it!=h.rend()&&count<31; it++, count++){
indices.push_back(*it);
}
reverse(indices.begin(), indices.end());
indices.push_back(n);
j=*indices.begin();
last_y=b[*indices.begin()];
for(int i=0;i<(int)indices.size()-1;i++){
prod*=a[indices[i]];
if(last_y<prod*b[indices[i]]){
last_y=b[indices[i]];
prod=1;
j=indices[i];
}
long long cur_y=que(1, 0, n-1, indices[i]+1, indices[i+1]-1, 1);
if(last_y<prod*cur_y){
last_y=cur_y;
prod=1;
j=indices[i];
}
}
return (que(1, 0, n-1, 0, j, 0)*last_y)%mod;
}
int init(int N, int X[], int Y[]){
n=N;
for(int i=0;i<n;i++){
a[i]=X[i];
if(a[i]>=2){
h.insert(i);
}
b[i]=Y[i];
}
build(1, 0, n-1);
//~ cout<<"ARR: ";
//~ for(int i=0;i<n;i++){
//~ cout<<que(1,0,n-1,i,i,1)<<" ";
//~ }
//~ cout<<endl;
//~ cout<<"MAX: "<<que(1,0,n-1,0,n-1,1)<<endl;
return calc();
}
int updateX(int pos, int val){
h.erase(pos);
a[pos]=val;
if(val>=2){
h.insert(pos);
}
upd(1,0,n-1,pos,pos,Node{val,-1});
return calc();
}
int updateY(int pos, int val){
b[pos]=val;
upd(1,0,n-1,pos,pos,Node{-1,val});
return calc();
}
