#include "horses.h"
#include <bits/stdc++.h>
#define N 500005
using namespace std;
const int mod = 1e9 + 7;
struct SegTree1{
vector<int> t;
int n;
void init(int size){
n = size;
t.assign(4*n,0);
}
void upd(int v,int tl,int tr,int pos,int val){
if(tl == tr){
t[v] = val;
return;
}
int tm = (tl + tr)/2;
if(pos <= tm){
upd(v*2,tl,tm,pos,val);
}
else upd(v*2+1,tm+1,tr,pos,val);
t[v] = (long long)t[v*2]*t[v*2+1]%mod;
}
int get(int v,int tl,int tr,int l,int r){
if(tr < l || r < tl){
return 1;
}
if(l <= tl && tr <= r){
return t[v];
}
int tm = (tl + tr)/2;
return (long long)get(v*2,tl,tm,l,r)*get(v*2+1,tm+1,tr,l,r)%mod;
}
void upd(int pos,int val){
upd(1,0,n-1,pos,val);
}
int get(int l,int r){
return get(1,0,n-1,l,r);
}
}tree1;
struct SegTree2{
vector<int> t;
int n;
void init(int size){
n = size;
t.assign(4*n,0);
}
void upd(int v,int tl,int tr,int pos,int val){
if(tl == tr){
t[v] = val;
return;
}
int tm = (tl + tr)/2;
if(pos <= tm){
upd(v*2,tl,tm,pos,val);
}
else upd(v*2+1,tm+1,tr,pos,val);
t[v] = max(t[v*2],t[v*2+1]);
}
int get(int v,int tl,int tr,int l,int r){
if(tr < l || r < tl){
return 1;
}
if(l <= tl && tr <= r){
return t[v];
}
int tm = (tl + tr)/2;
return max(get(v*2,tl,tm,l,r),get(v*2+1,tm+1,tr,l,r));
}
void upd(int pos,int val){
upd(1,0,n-1,pos,val);
}
int get(int l,int r){
return get(1,0,n-1,l,r);
}
}tree2;
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 = tree2.get(l,n-1);
if(prod * foo > val){
val = prod * foo;
opt = l;
}
if(s.upper_bound(l) == s.end())break;
l = *s.upper_bound(l);
}
return (long long)tree2.get(opt,n-1) * tree1.get(0,opt) % mod;
}
int init(int n_, int X[], int Y[]) {
n = n_;
tree1.init(n);
tree2.init(n);
for(int i = 0;i<n;i++){
x[i] = X[i];
y[i] = Y[i];
tree1.upd(i,x[i]);
tree2.upd(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;
tree1.upd(pos,x[pos]);
if(x[pos] > 1){
s.insert(pos);
}
return get_ans();
}
int updateY(int pos, int val) {
y[pos] = val;
tree2.upd(pos,y[pos]);
return get_ans();
}
