#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
#define maxn 500050
#define mod 1000000007
#define ll long long
#define f first
#define s second
#define ii pair<ll,ll>
#define db(x) cerr << #x << ": " << (x) << '\n';
struct node{
int my, px;
} st[maxn*4];
int x[maxn], y[maxn], n;
set<int> s;
node join(node a,node b){
return { max( a.my , b.my ) , (ll)a.px * b.px % mod };
}
void build(int nod,int l,int r){
if( l == r ){ st[nod] = { y[l] , x[l] }; return; }
int mi = ( l + r ) >> 1;
build(2*nod,l,mi);
build(2*nod+1,mi+1,r);
st[nod] = join( st[2*nod] , st[2*nod+1] );
}
void update(int nod,int l,int r,int id){
if( l == r ){ st[nod] = { y[l] , x[l] }; return; }
int mi = ( l + r ) >> 1;
if( id <= mi ) update(2*nod,l,mi,id);
else update(2*nod+1,mi+1,r,id);
st[nod] = join( st[2*nod] , st[2*nod+1] );
}
//int queryx(int nod,int l,int r,int xx,int yy){
//
// if( l > yy || r < xx || l > r ) return 0;
//
// if( l == r ){
// if( st[nod].mx > 1 ) return l;
// return 0;
// }
//
// int mi = ( l + r ) >> 1;
//
// if( l >= xx && r <= yy ){
// if( st[2*nod+1].mx > 1 )
// return queryx(2*nod+1,mi+1,r,xx,yy);
// if( st[2*nod].mx > 1 )
// return queryx(2*nod,l,mi,xx,yy);
// return 0;
// }
//
// return max( queryx(2*nod,l,mi,xx,yy) , queryx(2*nod+1,mi+1,r,xx,yy) );
//}
node queryy(int nod,int l,int r,int xx,int yy){
if( l > yy || r < xx || l > r ) return { 0 , 1 };
if( l >= xx && r <= yy ) return st[nod];
int mi = ( l + r ) >> 1;
return join( queryy(2*nod,l,mi,xx,yy) , queryy(2*nod+1,mi+1,r,xx,yy) );
}
int solve(){
ll res = (ll)x[n] * y[n];//db(res)
int id = n;
bool moduled = 0;
if( res < mod ){
for(int i=1; i<=32; i++){
int nid;
if( x[id-1] > 1 ) nid = id - 1;
else{
auto pnid = s.lower_bound(id);
if( pnid == s.begin() ){
nid = 0;
}
else{
pnid --;
nid = *pnid;
}
}
//db(nid)db(id)
if( nid == 0 ) break;
node f;
if( nid + 1 != id ) f = queryy(1,1,n,nid,id-1);
else f = { y[nid] , x[nid] };
res = max( res , (ll)f.my );
res *= f.px;
id = nid;
if( res >= mod ){
moduled = 1;
res %= mod;
break;
}
}
}
else{
res %= mod;
moduled = 1;
}
node cc = queryy(1,1,n,1,id-1);
res *= cc.px;
if( res >= mod ){
res %= mod;
moduled = 1;
}
if( !moduled ){
res = max( res , (ll)cc.my );
}
return res;
}
int init(int N, int X[], int Y[]) {
n = N;
for(int i=0; i<N; i++){
x[i+1] = X[i];
y[i+1] = Y[i];
if( x[i+1] > 1 ) s.insert(i+1);
}
build(1,1,N);
return solve();
}
int updateX(int pos, int val) {
x[pos+1] = val;
if( x[pos+1] == 1 ) s.erase(x[pos+1]);
if( x[pos+1] > 1 ) s.insert(x[pos+1]);
update(1,1,n,pos+1);
return solve();
}
int updateY(int pos, int val) {
y[pos+1] = val;
if( x[pos+1] == 1 ) s.erase(x[pos+1]);
if( x[pos+1] > 1 ) s.insert(x[pos+1]);
update(1,1,n,pos+1);
return solve();
}
