#include "horses.h"
#include<iostream>
#include<cmath>
using namespace std;
int n;
int x[500005];
long double v1[500005];
long double v2[500005];
long double ainty[2000005];
long double lazy[2000005];
long double posy[2000005];
long long prod[2000005];
long long mod=1e9+7;
void build(int node,int st,int dr)
{
lazy[node]=0;
ainty[node]=0;
if(st==dr)
{
posy[node]=st;
ainty[node]=v2[st];
prod[node]=x[st];
return ;
}
int mij=(st+dr)/2;
build(node*2,st,mij);
build(node*2+1,mij+1,dr);
posy[node]=posy[node*2];
prod[node]=(1ll*prod[node*2]*prod[node*2+1])%mod;
}
void push(int node,int st,int dr)
{
ainty[node]+=lazy[node];
if(st!=dr)
{
lazy[node*2]+=lazy[node];
lazy[node*2+1]+=lazy[node];
}
lazy[node]=0;
}
void updatey(int node,int st,int dr,int qst,int qdr,long double val)
{
push(node,st,dr);
if(st>dr || st>qdr || qst>dr || qst>qdr)
{
return ;
}
if(qst<=st && dr<=qdr)
{
lazy[node]=val;
push(node,st,dr);
return;
}
int mij=(st+dr)/2;
updatey(node*2,st,mij,qst,qdr,val);
updatey(node*2+1,mij+1,dr,qst,qdr,val);
ainty[node]=max(ainty[node*2],ainty[node*2+1]);
if(ainty[node]==ainty[node*2])
{
posy[node]=posy[node*2];
}
else
{
posy[node]=posy[node*2+1];
}
}
void updatex(int node,int st,int dr,int pos,long double val)
{
if(st>pos || pos>dr)
{
return ;
}
if(st==dr)
{
prod[node]=val;
return;
}
int mij=(st+dr)/2;
updatex(node*2,st,mij,pos,val);
updatex(node*2+1,mij+1,dr,pos,val);
prod[node]=(1ll*prod[node*2]*prod[node*2+1])%mod;
}
long long query(int node,int st,int dr,int qst,long double qdr)
{
if(st>dr || st>qdr || qst>dr || qst>qdr)
{
return 1;
}
if(qst<=st && dr<=qdr)
{
return prod[node];
}
int mij=(st+dr)/2;
long long r1,r2;
r1=query(node*2,st,mij,qst,qdr);
r2=query(node*2+1,mij+1,dr,qst,qdr);
return (1ll*r1*r2)%mod;
}
int y[500005];
long long eval()
{
int pos=posy[1];
return (y[pos]*query(1,0,n-1,0,pos))%mod;
}
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];
v1[i]=log((long double)x[i]);
v2[i]=log((long double)y[i]);
}
build(1,0,n-1);
for(int i=0;i<n;i++)
{
updatey(1,0,n-1,i,n-1,v1[i]);
}
return eval();
}
int updateX(int pos, int val) {
long double diff=v1[pos];
x[pos]=val;
v1[pos]=log((long double)x[pos]);
updatey(1,0,n-1,pos,n-1,v1[pos]-diff);
updatex(1,0,n-1,pos,x[pos]);
return eval();
}
int updateY(int pos, int val) {
long double diff=v2[pos];
y[pos]=val;
v2[pos]=log((long double)y[pos]);
updatey(1,0,n-1,pos,pos,v2[pos]-diff);
return eval();
}
