#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;
// if(query(1,0,n-1,0,n-1).flag==false){
// int ant=-1;
// for(int x : s){
// }
// }
int id=bb(1,0,n-1,1ll), ant=id;
ll P=x[id];
auto f=s.upper_bound(id);
while(f!=s.end()){
int at=*f;
resp=max(resp,P*query(1,0,n-1,ant,at-1).ma);
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 init(int N, int X[], int Y[]){
// cerr << "iniciado\n";
s.insert(n);
nulo.prod=1; nulo.ma=1; nulo.flag=false;
n=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();
}
