#pragma once
#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7, MAXN=500005;
long long X[MAXN], Y[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=X[v];
st[v].rmq=Y[v];
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 x){
if(e<ts||s>te){
return;
}else if(ts<=s&&e<=te){
if(x.rmq==-1){
st[v].prod=x.prod;
}else st[v].rmq=x.rmq;
return;
}
int m=(s+e)/2;
upd(v*2, s, m, ts, te, x);
upd(v*2+1, m+1, e, ts, te, x);
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;
}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=max(0, n-31), count=0;
long long prod=1, last_y=Y[j];
vector<int> indices;
for(auto it=h.rbegin(); it!=h.rend()&&count<30; it++, count++){
indices.push_back(*it);
}
reverse(indices.begin(), indices.end());
indices.push_back(n);
for(int i=0;i<(int)indices.size()-1;i++){
if(last_y<prod*Y[i]){
last_y=Y[i];
prod=1;
j=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=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++){
X[i]=x[i];
if(x[i]>=2){
h.insert(i);
}
Y[i]=y[i];
}
build(1, 0, n-1);
return calc();
}
int updateX(int pos, int val){
h.erase(pos);
X[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){
Y[pos]=val;
upd(1,0,n-1,pos,pos,Node{-1,val});
return calc();
}
