#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF (ll)1000000005//biggest than max Y
#define MOD (ll)1000000007//modulo for evaluation
#define MAXN 500005
ll x[MAXN],y[MAXN];
int mxst[4*MAXN];
pair<ll,ll> prst[4*MAXN];//(real,mod);
int n;
ll pr(ll a,ll b){
return ((a*b)>=INF)?INF:(a*b);
}
ll prmod(ll a,ll b){
return (a*b)%MOD;
}
pair<ll,ll> pr(pair<ll,ll> a,pair<ll,ll> b){
return {pr(a.first,b.first),prmod(a.second,b.second)};
}
void prbuild(int v=1,int start=0,int end=n-1){
if(start==end){
prst[v]={x[start],x[start]};
return;
}
int mid=(start+end)/2;
prbuild(2*v,start,mid);
prbuild(2*v+1,mid+1,end);
prst[v]=pr(prst[2*v],prst[2*v+1]);
}
void prupdate(int pos,int v=1,int start=0,int end=n-1){
if(start==end){
prst[v]={x[start],x[start]};
return;
}
int mid=(start+end)/2;
if(pos<=mid){
prupdate(pos,2*v,start,mid);
}else{
prupdate(pos,2*v+1,mid+1,end);
}
prst[v]=pr(prst[2*v],prst[2*v+1]);
}
pair<ll,ll> prquery(int from,int to,int v=1,int start=0,int end=n-1){
if(start==from&&end==to){
return prst[v];
}
int mid=(start+end)/2;
if(to<=mid){
return prquery(from,to,2*v,start,mid);
}else if(from>mid){
return prquery(from,to,2*v+1,mid+1,end);
}else{
return pr(prquery(from,mid,2*v,start,mid),prquery(mid+1,to,2*v+1,mid+1,end));
}
}
int mx(int i,int j){//i<j
return (y[i]>pr(prquery(i+1,j).first,y[j]))?i:j;
}
void mxbuild(int v=1,int start=0,int end=n-1){
if(start==end){
mxst[v]=start;
return;
}
int mid=(start+end)/2;
mxbuild(2*v,start,mid);
mxbuild(2*v+1,mid+1,end);
mxst[v]=mx(mxst[2*v],mxst[2*v+1]);
}
void mxupdate(int pos,int v=1,int start=0,int end=n-1){
if(start==end){
mxst[v]=start;
return;
}
int mid=(start+end)/2;
if(pos<=mid){
mxupdate(pos,2*v,start,mid);
}else{
mxupdate(pos,2*v+1,mid+1,end);
}
mxst[v]=mx(mxst[2*v],mxst[2*v+1]);
}
int evaluate(){
int i=mxst[1];
return prmod(prquery(0,i).second,y[i]);
}
int init(int N, int X[], int Y[]) {
n=N;
for(int i=0;i<n;i++){
x[i]=X[i];
y[i]=Y[i];
}
prbuild();
mxbuild();
return evaluate();
}
int updateX(int pos, int val) {
x[pos]=val;
prupdate(pos);
mxupdate(pos);
return evaluate();
}
int updateY(int pos, int val) {
y[pos]=val;
mxupdate(pos);
return evaluate();
}
