#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n;
vector<ll> x,y;
const ll inf=1e9;
const ll mod=1e9+7;
vector<ll> segtree,segtreemx;
set<int> S;
void update(int pos,int val,int l=0,int r=n-1,int v=1){
if(l==r){
segtree[v]=val;
return;
}
int mid=(l+r)/2;
if(pos<=mid) update(pos,val,l,mid,v*2);
else update(pos,val,mid+1,r,v*2+1);
segtree[v]=segtree[v*2]*segtree[v*2+1]%mod;
}
ll query(int tl,int tr,int l=0,int r=n-1,int v=1){
if(r<tl or tr<l){
return 1;
}
if(tl<=l and r<=tr){
return segtree[v];
}
int mid=(l+r)/2;
return query(tl,min(mid,tr),l,mid,v*2)*query(max(mid+1,tl),tr,mid+1,r,v*2+1)%mod;
}
void updatemx(int pos,int val,int l=0,int r=n-1,int v=1){
if(l==r){
segtreemx[v]=val;
return;
}
int mid=(l+r)/2;
if(pos<=mid) updatemx(pos,val,l,mid,v*2);
else updatemx(pos,val,mid+1,r,v*2+1);
segtreemx[v]=max(segtreemx[v*2],segtreemx[v*2+1]);
}
ll querymx(int tl,int tr,int l=0,int r=n-1,int v=1){
if(r<tl or tr<l){
return 0;
}
if(tl<=l and r<=tr){
return segtreemx[v];
}
int mid=(l+r)/2;
return max(querymx(tl,min(mid,tr),l,mid,v*2),querymx(max(mid+1,tl),tr,mid+1,r,v*2+1));
}
ll go(){
ll cur=0;
int prv=n;
ll ans=1;
int best=-1;
for(auto it=S.rbegin();it!=S.rend();it++){
int pos=*it;
ll mx=querymx(max(pos,0),prv-1);
//return mx;
if(mx>cur){
cur=mx;
ans=query(0,pos)*mx%mod;
best=pos;
//if(pos==0) return query(0,pos);
}
if(pos!=-1){
if(cur*x[pos]>inf) break;
cur*=x[pos];
}
prv=pos;
}
return ans;
}
int init(int N, int X[], int Y[]) {
n=N;
x.resize(n);
y.resize(n);
segtree=vector<ll>(4*n,1);
segtreemx=vector<ll>(4*n,1);
S.insert(-1);
for(int i=0;i<n;i++){
x[i]=X[i];
y[i]=Y[i];
update(i,x[i]);
updatemx(i,y[i]);
if(x[i]>1) S.insert(i);
}
return go();
}
int updateX(int pos, int val) {
if(x[pos]>1) S.erase(pos);
x[pos]=val;
if(x[pos]>1) S.insert(pos);
update(pos,x[pos]);
return go();
}
int updateY(int pos, int val) {
y[pos]=val;
updatemx(pos,y[pos]);
return go();
}
