#include "horses.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=5e5+10;
const int mod=1e9+7;
int n;
int x[maxn], y[maxn];
set<int>s;
struct node{
ll prod, ma;
bool flag;
};
node seg[4*maxn], nulo;
node merge(node e, node d){
node ret; ret.flag=false;
ret.prod=e.prod*d.prod;
if(ret.prod>mod) ret.flag=true;
ret.prod%=mod;
ret.flag|=e.flag|d.flag;
ret.ma=max(e.ma,d.ma);
return ret;
}
void update(int id, int ini, int fim, int cara){
if(ini==fim){
seg[id].prod=x[ini];
seg[id].ma=y[ini];
seg[id].flag=false;
return;
}
int mid=(ini+fim)/2, e=2*id, d=2*id+1;
if(cara<=mid) update(e,ini,mid,cara);
else update(d,mid+1,fim,cara);
seg[id]=merge(seg[e],seg[d]);
}
node query(int id, int ini, int fim, int l, int r){
if(l>r) return nulo;
if(ini>r||fim<l) return nulo;
if(l<=ini&&fim<=r) return seg[id];
int mid=(ini+fim)/2, e=2*id, d=2*id+1;
return merge(query(e,ini,mid,l,r),query(d,mid+1,fim,l,r));
}
int bb(int id, int ini, int fim, ll c){
if(ini==fim) return ini;
int mid=(ini+fim)/2, e=2*id, d=2*id+1;
if(seg[d].flag||seg[d].prod*c>mod) return bb(d,mid+1,fim,c);
return bb(e,ini,mid,c*seg[d].prod);
}
// int calc(){
// ll resp=0;
// int id=bb(1,0,n-1,1ll), ant=id;
// ll P=x[id];
// // cerr << "! " << id << ' ' << P << '\ n';
// auto f=s.upper_bound(id);
// while(f!=s.end()){
// int at=*f;
// // cerr << "yay " << at << '\n';
// resp=max(resp,P*query(1,0,n-1,ant,at-1).ma);
// // cerr << resp << ' ' << P*query(1,0,n-1,ant,at-1).ma << ' ' << query(1,0,n-1,ant,at-1).ma << '\n';
// P*=x[at]; ant=at;
// f++;
// }
// resp%=mod; resp*=query(1,0,n-1,0,id-1).prod; resp%=mod;
// int ret=resp;
// // cerr << "calculado: " << ret << '\n';
// return ret;
// }
int calc(){
ll resp=0, prod=1, id=0;
for(int i=n-1;i>=0;i--){
prod*=x[i];
if(prod>mod){
id=i+1;
break;
}
}
resp=y[id];
prod=query(1,0,n-1,0,id).prod; prod%=mod;
ll at=1;
for(int i=id+1;i<n;i++){
at*=x[i];
resp=max(resp,at*y[i]);
}
resp%=mod;
resp*=prod;
resp%=mod;
int ret=resp;
return ret;
}
int init(int N, int X[], int Y[]){
// cerr << "iniciado\n";
nulo.prod=1; nulo.ma=1; nulo.flag=false;
n=N;
s.insert(n);
for(int i=0;i<n;i++){
x[i]=X[i]; y[i]=Y[i];
if(x[i]>1) s.insert(i);
update(1,0,n-1,i);
}
// cerr << "so calcular\n";
return calc();
}
int updateX(int pos, int val){
if(x[pos]>1) s.erase(pos);
x[pos]=val;
if(x[pos]>1) s.insert(pos);
update(1,0,n-1,pos);
return calc();
}
int updateY(int pos, int val){
y[pos]=val;
update(1,0,n-1,pos);
return calc();
}
