#include "horses.h"
#include <bits/stdc++.h>
#define N 500005
using namespace std;
const int mod = 1e9 + 7;
struct node{
int maxi;
int prod = 1;
node(int a,int b){
maxi = a;
prod = b;
}
};
node merge(node a,node b){
a.prod = (long long)a.prod * b.prod %mod;
a.maxi = max(a.maxi,b.maxi);
return a;
}
struct SegTree{
vector<node> t;
int n;
void init(int size){
n = size;
t.assign(4*n,node(0,1));
}
void upd1(int v,int tl,int tr,int pos,int val){
if(tl == tr){
t[v].prod = val;
return;
}
int tm = (tl + tr)/2;
if(pos <= tm){
upd1(v*2,tl,tm,pos,val);
}
else upd1(v*2+1,tm+1,tr,pos,val);
t[v] = merge(t[v*2],t[v*2+1]);
}
void upd2(int v,int tl,int tr,int pos,int val){
if(tl == tr){
t[v].maxi = val;
return;
}
int tm = (tl + tr)/2;
if(pos <= tm){
upd2(v*2,tl,tm,pos,val);
}
else upd2(v*2+1,tm+1,tr,pos,val);
t[v] = merge(t[v*2],t[v*2+1]);
}
node get(int v,int tl,int tr,int l,int r){
if(tr < l || r < tl){
return node(0,1);
}
if(l <= tl && tr <= r){
return t[v];
}
int tm = (tl + tr)/2;
return merge(get(v*2,tl,tm,l,r),get(v*2+1,tm+1,tr,l,r));
}
void upd1(int pos,int val){
upd1(1,0,n-1,pos,val);
}
void upd2(int pos,int val){
upd2(1,0,n-1,pos,val);
}
node get(int l,int r){
return get(1,0,n-1,l,r);
}
}tree;
const int BOUND = 1e9;
set<int> s;
int x[N],y[N];
int n;
int get_ans(){
int l = 0;
long long prod = 1;
if(s.size()){
auto it = prev(s.end());
while(prod < BOUND){
prod *= x[*it];
if(prod >= BOUND){
l = *it;
}
if(it == s.begin())break;
it = prev(it);
}
}
int tmp = l;
int opt = l;
long long val = 0;
prod = 1;
while(1){
if(l != tmp){
prod *= x[l];
}
auto foo = tree.get(l,n-1);
if(prod * foo.maxi > val){
val = prod * foo.maxi;
opt = l;
}
if(s.upper_bound(l) == s.end())break;
l = *s.upper_bound(l);
}
return (long long)tree.get(opt,n-1).maxi * tree.get(0,opt).prod % mod;
}
int init(int n_, int X[], int Y[]) {
n = n_;
tree.init(n);
for(int i = 0;i<n;i++){
x[i] = X[i];
y[i] = Y[i];
tree.upd1(i,x[i]);
tree.upd2(i,y[i]);
if(x[i] > 1){
s.insert(i);
}
}
return get_ans();
}
int updateX(int pos, int val) {
if(x[pos] > 1){
s.erase(pos);
}
x[pos] = val;
tree.upd1(pos,x[pos]);
if(x[pos] > 1){
s.insert(pos);
}
return get_ans();
}
int updateY(int pos, int val) {
y[pos] = val;
tree.upd2(pos,y[pos]);
return get_ans();
}
