#include "horses.h"
#include <bits/stdc++.h>
#define lc v<<1
#define rc v<<1|1
using ll = long long int;
using namespace std;
const int MOD = 1000000007, MN = 5e5 + 10;
ll pow(ll x, ll y, ll mod){
ll ans=1;
while (y != 0) {
if (y & 1) ans = ans * x % mod;
y >>= 1;
x = x * x % mod;
}
return ans;
}
ll f[MN*4],g[MN],RX[MN];
int n;
set<int> st;
void update(int v, int l, int r, int p, ll x){
if(r-l==1){
f[v]=x;
return;
}
int m=(l+r)>>1;
if(p<m) update(lc,l,m,p,x);
else update(rc,m,r,p,x);
f[v]=max(f[lc],f[rc]);
}
ll get(int v, int l, int r, int tl, int tr){
if(l>=tr || tl>=r || tl>=tr) return 0;
if(l>=tl && r<=tr) return f[v];
int m=(l+r)>>1;
return max(get(lc,l,m,tl,tr),get(rc,m,r,tl,tr));
}
void upd(int t, ll x){
for(t+=5; t<MN; t+=t&-t) g[t]=g[t]*x%MOD;
}
ll gt(int t, ll x=1){
for(t+=5; t; t-=t&-t) x=x*g[t]%MOD;
return x;
}
int init(int N, int X[], int Y[]) {
n=N;
st.clear();
for(ll i=0; i<MN; i++) g[i]=1;
for(int i=0; i<N; i++){
update(1,0,n,i,Y[i]);
upd(i,X[i]);
RX[i]=X[i];
if(X[i]>1) st.insert(-i);
}
ll ans=0,k=-1;
for(int t : st){
if(ans>(ll)1e9) break;
t=-t;
k=t;
ans=max(ans,get(1,0,n,t,n));
ans*=RX[t];
}
ans=ans%MOD*gt(k-1)%MOD;
if(k==-1) return f[1];
return ans;
}
int updateX(int pos, int val) {
ll x=pow(RX[pos],MOD-2,MOD)*val%MOD;
upd(pos,x);
RX[pos]=val;
if(val>1) st.insert(-pos);
else st.erase(-pos);
ll ans=0,k=-1;
for(int t : st){
if(ans>(ll)1e9) break;
t=-t;
k=t;
ans=max(ans,get(1,0,n,t,n));
ans*=RX[t];
}
ans=ans%MOD*gt(k-1)%MOD;
if(k==-1) return f[1];
return ans;
}
int updateY(int pos, int val) {
update(1,0,n,pos,val);
ll ans=0,k=-1;
for(int t : st){
if(ans>(ll)1e9) break;
t=-t;
k=t;
ans=max(ans,get(1,0,n,t,n));
ans*=RX[t];
}
ans=ans%MOD*gt(k-1)%MOD;
if(k==-1) return f[1];
return ans;
}
