#include "horses.h"
#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <utility>
#include <stack>
#include <vector>
#include <fstream>
#include <set>
#include <map>
using namespace std;
const int mod=1e9+7;
typedef long long int ll;
vector<ll>lx;
vector<ll>ly;
vector<ll>mu;
vector<ll>ma;
set<int>s;
int hI(int p){
return p<<2;
}
int hD(int p){
return (p<<2)+1;
}
void buildmu(int nodo,int L,int R){
if(L<R){
int m=L+(R-L)/2;
buildmu(hI(nodo),L,m);
buildmu(hD(nodo),m+1,R);
mu[nodo]=(mu[hI(nodo)]*mu[hD(nodo)])%mod;
}
else{
mu[nodo]=lx[L];
}
}
void buildma(int nodo,int L,int R){
if(L<R){
int m=L+(R-L)/2;
buildma(hI(nodo),L,m);
buildma(hD(nodo),m+1,R);
ma[nodo]=max(ma[hI(nodo)],ma[hD(nodo)]);
}
else{
ma[nodo]=ly[L];
}
}
ll vama(int L,int R,int st,int fi,int nodo){
if(L>=st && R<=fi)return ma[nodo];
else if(st>R || fi<L)return -1;
else{
int m=L+(R-L)/2;
ll v1=vama(L,m,st,fi,hI(nodo));
ll v2=vama(m+1,R,st,fi,hD(nodo));
return max(v1,v2);
}
}
ll vamu(int L,int R,int st,int fi,int nodo){
if(L>=st && R<=fi)return mu[nodo];
else if(st>R || fi<L)return 1;
else{
int m=L+(R-L)/2;
ll v1=vamu(L,m,st,fi,hI(nodo));
ll v2=vamu(m+1,R,st,fi,hD(nodo));
return (v1*v2)%mod;
}
}
void upY(int nodo,int L,int R,int b,ll n){
if(b<L||b>R)return;
else if(L==R){
ly[b]=n;
ma[nodo]=n;
}
else{
int m=L+(R-L)/2;
upY(hI(nodo),L,m,b,n);
upY(hD(nodo),m+1,R,b,n);
ma[nodo]=max(ma[hI(nodo)],ma[hD(nodo)]);
}
}
void upX(int nodo,int L,int R,int b,ll n){
if(b<L||b>R)return;
else if(L==R){
lx[b]=n;
mu[nodo]=n;
}
else{
int m=L+(R-L)/2;
upX(hI(nodo),L,m,b,n);
upX(hD(nodo),m+1,R,b,n);
mu[nodo]=(mu[hI(nodo)]*mu[hD(nodo)])%mod;
}
}
int solve(){
int n=lx.size();
ll l,r=n-1,a=0,me=0;
for(ll k:s){
l=-1*k;
a=vama(0,n-1,l,r,1);
me=max(me,a);
me*=lx[l];
r=l-1;
if(me>1e9||l==0)break;
}
me%=mod;
if(r>=0){
me=(me*vamu(0,n-1,0,r,1))%mod;
}
return me;
}
int init(int N, int X[], int Y[]) {
lx.resize(N);
ly.resize(N);
mu.resize(4*N);
ma.resize(4*N);
for(int i=0;i<N;i++){
lx[i]=X[i];
ly[i]=Y[i];
if(X[i]>1){
s.insert(-i);
}
}
s.insert(0);
buildmu(1,0,N-1);
buildma(1,0,N-1);
return solve();
}
int updateX(int pos, int val) {
int n=lx.size();
if(pos!=0){
ll j=lx[pos];
if(j==1 && val>1){
s.erase(-pos);
}
else if(val==1){
s.insert(-pos);
}
}
lx[pos]=val;
upX(1,0,n-1,pos,val);
return solve();
}
int updateY(int pos, int val) {
int n=lx.size();
ly[pos]=val;
upY(1,0,n-1,pos,val);
return solve();
}
