#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> ii;
#define mod 1000000007
struct node{
int s,e,m;ll v=1,lz=1;
node *l,*r;
node(int _s,int _e){
s=_s,e=_e,m=(s+e)>>1;
if(s!=e)l=new node(s,m),r=new node(m+1,e);
}
void ppo(){
v=(v*lz)%mod;
if(s!=e){
l->lz=(lz*l->lz)%mod;
r->lz=(lz*r->lz)%mod;
}
lz=1;
}
void up(int x,int y,ll nv){
if(s==x&&e==y){lz=(lz*nv)%mod;return;}
if(y<=m)l->up(x,y,nv);
else if(x>m)r->up(x,y,nv);
else l->up(x,m,nv),r->up(m+1,y,nv);
l->ppo(),r->ppo();
v=max(l->v,r->v);
}
ll qry(int x,int y){
ppo();
if(s==x&&e==y)return v;
if(y<=m)return l->qry(x,y);
if(x>m)return r->qry(x,y);
return max(l->qry(x,m),r->qry(m+1,y));
}
void print(){
printf("%d %d %d %lld %lld\n",s,e,m,v,lz);
if(s!=e)l->print(),r->print();
}
}*rt;
struct node2{
int s,e,m;ll v=1,lz=1;
node2 *l,*r;
node2(int _s,int _e){
s=_s,e=_e,m=(s+e)>>1;
if(s!=e)l=new node2(s,m),r=new node2(m+1,e);
}
void ppo(){
v=(v*lz)%mod;
if(s!=e){
l->lz=(lz*l->lz)%mod;
r->lz=(lz*r->lz)%mod;
}
lz=1;
}
void up(int x,int y,ll nv){
if(s==x&&e==y){lz=(lz*nv)%mod;return;}
if(y<=m)l->up(x,y,nv);
else if(x>m)r->up(x,y,nv);
else l->up(x,m,nv),r->up(m+1,y,nv);
l->ppo(),r->ppo();
v=(l->v*r->v)%mod;
}
ll qry(int x,int y){
ppo();
if(s==x&&e==y)return v;
if(y<=m)return l->qry(x,y);
if(x>m)return r->qry(x,y);
return (l->qry(x,m)*r->qry(m+1,y))%mod;
}
void print(){
printf("%d %d %d %lld %lld\n",s,e,m,v,lz);
if(s!=e)l->print(),r->print();
}
}*pfx;
struct node3{
int s,e,m,v;
node3 *l,*r;
node3(int _s,int _e){
s=_s,e=_e,m=(s+e)>>1,v=0;
if(s!=e)l=new node3(s,m),r=new node3(m+1,e);
}
void up(int x,ll nv){
if(s==x&&e==x){v=nv;return;}
if(x<=m)l->up(x,nv);
else r->up(x,nv);
v=max(l->v,r->v);
}
ll qry(int x,int y){
if(s==x&&e==y)return v;
if(y<=m)return l->qry(x,y);
if(x>m)return r->qry(x,y);
return max(l->qry(x,m),r->qry(m+1,y));
}
void print(){
printf("%d %d %d %lld\n",s,e,m,v);
if(s!=e)l->print(),r->print();
}
}*yrt;
ll fp(ll x,int a){
if(a==0)return 1;
ll t=fp(x,a/2);
ll r=(t*t)%mod;
if(a%2)r=(r*x)%mod;
return r;
}
#define maxn 500005
int n,x[maxn],y[maxn];
set<ii> s;
int ans(){
auto it=s.end();
ll mx=1;
int pv=n;
while(it!=s.begin()){
--it;
auto[i,x]=*it;
//check if [i,n-1] can be >1e9
mx=max(mx,yrt->qry(i,pv-1));
mx*=x;
if(mx>1e9){
if(i==0)return mx%mod;
ll f=pfx->qry(0,i-1);
return (f*(mx%mod))%mod;
}
pv=i;
}
return rt->qry(0,n-1);
}
int init(int N,int X[],int Y[]){
n=N;
rt=new node(0,n-1);
pfx=new node2(0,n-1);
yrt=new node3(0,n-1);
for(int i=0;i<n;++i){
x[i]=X[i],y[i]=Y[i];
rt->up(i,n-1,x[i]);
pfx->up(i,i,x[i]);
rt->up(i,i,y[i]);
yrt->up(i,y[i]);
if(x[i]!=1)s.insert({i,x[i]});
}
return ans();
}
int updateX(int pos,int val){
if(x[pos]!=1)s.erase({pos,x[pos]});
rt->up(pos,n-1,fp(x[pos],mod-2));
pfx->up(pos,pos,fp(x[pos],mod-2));
rt->up(pos,n-1,val);
pfx->up(pos,pos,val);
x[pos]=val;
if(val!=1)s.insert({pos,val});
return ans();
}
int updateY(int pos,int val){
rt->up(pos,pos,fp(y[pos],mod-2));
rt->up(pos,pos,val);
yrt->up(pos,val);
y[pos]=val;
return ans();
}
