#include "horses.h"
#include <bits/stdc++.h>
#define pb push_back
#define ET cout << "\n"
#define ALL(v) v.begin(),v.end()
#define MP make_pair
#define F first
#define S second
#define MEM(i,j) memset(i,j,sizeof i)
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
ll cross(ll a,ll aB,ll b,ll bB,ll &B)
{
if(aB||bB||a*b>MOD) B=1;
else B=0;
return a*b%MOD;
}
ll n,y[500005];
struct node
{
ll crs,mx,L,R,Lb,Rb,B;
node operator+(const node &a)const{
node re;
re.crs=cross(crs,B,a.crs,a.B,re.B);
if(Rb||a.Lb||R*a.L>MOD||R*a.L*y[a.mx]>=y[mx])
{
re.mx=a.mx;
re.L=cross(crs,B,a.L,a.Lb,re.Lb);
re.R=a.R,re.Rb=a.Rb;
}
else
{
re.mx=mx;
re.L=L,re.Lb=Lb;
re.R=cross(a.crs,a.B,R,Rb,re.Rb);
}
return re;
}
}seg[2000000];
void build(ll l,ll r,ll rt,int X[])
{
if(l==r)
return seg[rt]=node{(ll)X[l],l,(ll)X[l],1LL,0LL,0LL,0LL},void();
ll m=l+r>>1;
build(l,m,rt<<1,X),build(m+1,r,rt<<1|1,X);
seg[rt]=seg[rt<<1]+seg[rt<<1|1];
}
void modifyx(ll x,ll l,ll r,ll rt,ll v)
{
if(l==r)
return seg[rt]=node{v,l,v,1LL,0LL,0LL,0LL},void();
ll m=l+r>>1;
if(x<=m) modifyx(x,l,m,rt<<1,v);
else modifyx(x,m+1,r,rt<<1|1,v);
seg[rt]=seg[rt<<1]+seg[rt<<1|1];
}
void modifyy(ll x,ll l,ll r,ll rt,ll v)
{
if(l==r)
return y[x]=v,void();
ll m=l+r>>1;
if(x<=m) modifyy(x,l,m,rt<<1,v);
else modifyy(x,m+1,r,rt<<1|1,v);
seg[rt]=seg[rt<<1]+seg[rt<<1|1];
}
ll query(ll L,ll R,ll l,ll r,ll rt)
{
if(L<=l&&R>=r)
return seg[rt].crs;
ll m=l+r>>1;
if(R<=m) return query(L,R,l,m,rt<<1);
if(L>m) return query(L,R,m+1,r,rt<<1|1);
return query(L,R,l,m,rt<<1)*query(L,R,m+1,r,rt<<1|1)%MOD;
}
int init(int N, int X[], int Y[])
{
n=N;
for(int i=0;i<N;++i)
y[i]=Y[i];
build(0,n-1,1,X);
return y[seg[1].mx]*query(0,seg[1].mx,0,n-1,1)%MOD;
}
int updateX(int pos, int val)
{
modifyx(pos,0,n-1,1,val);
return y[seg[1].mx]*query(0,seg[1].mx,0,n-1,1)%MOD;
}
int updateY(int pos, int val)
{
modifyy(pos,0,n-1,1,val);
return y[seg[1].mx]*query(0,seg[1].mx,0,n-1,1)%MOD;
}
