#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int lld;
typedef long double lf;
#define MOD 1000000007LL
#define INF 1000000000000000000LL
lld n;
vector<lld> x, y;
set<lld> big;
struct itemX{
lld val;
itemX(){
val = 0;
}
itemX(lld valval){
val=valval;
val%=MOD;
}
};
itemX merge(itemX a, itemX b){
lld res = a.val*b.val; res%=MOD;
return itemX(res);
}
itemX build_leaf(lld xxx){
return itemX(xxx);
}
itemX X_NEUT = itemX(1);
struct STX{
vector<itemX> st;
void init(){
lld sz = 1;
while(sz<n) sz*=2;
st.resize(2*sz);
}
void build(lld v = 1, lld tl = 0, lld tr = n-1){
if(tl==tr) st[v] = build_leaf(x[tl]);
else{
lld tm = (tl+tr)/2;
build(2*v, tl, tm);
build(2*v+1,tm+1,tr);
st[v] = merge(st[2*v], st[2*v+1]);
}
}
itemX query(lld l, lld r, lld v = 1, lld tl=0, lld tr=n-1){
if(l>r) return X_NEUT;
if(l==tl&&r==tr) return st[v];
lld tm = (tl+tr)/2;
return merge(query(l,min(r,tm),2*v, tl, tm),query(max(l, tm+1), r, 2*v+1, tm+1,tr));
}
void upd(lld new_val, lld pos, lld v=1,lld tl=0, lld tr=n-1){
if(tl==tr) st[v] = build_leaf(new_val);
else{
lld tm = (tl+tr)/2;
if(pos<=tm) upd(new_val, pos, 2*v, tl, tm);
else upd(new_val, pos, 2*v+1,tm+1,tr);
st[v] = merge(st[2*v],st[2*v+1]);
}
}
};
struct itemY{
lld val, ind;
itemY(){
val=-INF;
ind = -1;
}
itemY(lld valval, lld indind){
val=valval, ind=indind;
}
};
itemY merge(itemY a, itemY b){
return a.val>b.val?a:b;
}
itemY build_leaf(lld xxx, lld indind){
return itemY(xxx,indind);
}
itemY Y_NEUT = itemY(-INF,-1);
struct STY{
vector<itemY> st;
void init(){
lld sz = 1;
while(sz<n) sz*=2;
st.resize(2*sz);
}
void build(lld v = 1, lld tl = 0, lld tr = n-1){
if(tl==tr) st[v] = build_leaf(y[tl], tl);
else{
lld tm = (tl+tr)/2;
build(2*v, tl, tm);
build(2*v+1,tm+1,tr);
st[v] = merge(st[2*v], st[2*v+1]);
}
}
itemY query(lld l, lld r, lld v = 1, lld tl=0, lld tr=n-1){
if(l>r) return Y_NEUT;
if(l==tl&&r==tr) return st[v];
lld tm = (tl+tr)/2;
return merge(query(l,min(r,tm),2*v, tl, tm),query(max(l, tm+1), r, 2*v+1, tm+1,tr));
}
void upd(lld new_val, lld pos, lld v=1,lld tl=0, lld tr=n-1){
if(tl==tr) st[v] = build_leaf(new_val, tl);
else{
lld tm = (tl+tr)/2;
if(pos<=tm) upd(new_val, pos, 2*v, tl, tm);
else upd(new_val, pos, 2*v+1,tm+1,tr);
st[v] = merge(st[2*v],st[2*v+1]);
}
}
};
STX segx;
STY segy;
int calc(){
auto it = big.end();
for(int i=0;i<31;i++){
if(it==big.begin()) break;
--it;
}
auto it2 = it; ++it2;
lld next_pos = it2==big.end()?n:(*it2);
itemY mxY = segy.query((*it), next_pos-1);
lf cur = log((lf)x[(*it)])+log((lf)mxY.val);
lf mx = cur;
lld mx_pos = mxY.ind;
lld prevY = mxY.ind;
++it;
while(it!=big.end()){
cur -= log((lf)y[prevY]);
it2 = it; ++it2;
next_pos = it2==big.end()?n:(*it2);
mxY = segy.query((*it), next_pos-1);
cur += log((lf)x[(*it)])+log((lf)mxY.val);
if(cur>mx){
mx = cur;
mx_pos = mxY.ind;
}
prevY = mxY.ind;
++it;
}
lld res = segx.query(0, mx_pos).val;
res *= y[mx_pos]; res%=MOD;
return (int)res;
}
int init(int N, int X[], int Y[]) {
n = (lld) N;
x.resize(n); y.resize(n);
big.insert(0);
for(lld i=0;i<n;i++){
x[i] = (lld)X[i]; y[i] = (lld)Y[i];
if(x[i]>1) big.insert(i);
}
segx.init(); segx.build();
segy.init(); segy.build();
return calc();
}
int updateX(int pos, int val){
segx.upd(val, pos);
x[pos] = val;
if(val>1){
big.insert(pos);
}else if(pos!=0){
auto it = big.find(pos);
if(it!=big.end()) big.erase(it);
}
return calc();
}
int updateY(int pos, int val){
segy.upd(val, pos);
y[pos] = val;
return calc();
}
