#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
const ll mod=1e9+7;
ll fen[500001];
ll quick(ll a, ll m) {
ll ans=1;
while (m) {
if (m%2==1) ans=(ans*a)%mod;
a=(a*a)%mod;
m/=2;
}
return ans;
}
ll find_fen(int x) {
ll mul=1;
while (x) {
mul=(mul*fen[x])%mod;
x-=(x&-x);
}
return mul;
}
void update_fen(int x, ll ol, ll ne) {
while (x<=n) {
fen[x]=(fen[x]*quick(ol,mod-2))%mod;
fen[x]=(fen[x]*ne)%mod;
x+=(x&-x);
}
}
ll ms[1<<20],x[500001],y[500001];
void update_ms(int l, int r, int idx, int x, ll val) {
if (l>x || x>r) return;
if (l==r) ms[idx]=val;
else {
int mid=(l+r)/2;
update_ms(l,mid,2*idx,x,val);
update_ms(mid+1,r,2*idx+1,x,val);
if (ms[2*idx]==-1 || ms[2*idx+1]==-1) ms[idx]=-1;
else {
if (ms[2*idx]*ms[2*idx+1]>1e9) ms[idx]=-1;
else ms[idx]=ms[2*idx]*ms[2*idx+1];
}
}
}
ll query_ms(int l, int r, int idx, int x, int y) {
if (l>y || r<x) return 1;
if (x<=l && r<=y) return ms[idx];
int mid=(l+r)/2;
ll ml=query_ms(l,mid,2*idx,x,y), mr=query_ms(mid+1,r,2*idx+1,x,y);
if (ml==-1 || mr==-1) return -1;
else {
if (ml*mr>1e9) return -1;
else return ml*mr;
}
}
int check(int a, int b) { //whether who is bigger between s[a] and a[b]
ll h=query_ms(0,n-1,1,a+1,b);
if (h==-1) return b;
if (y[a]>y[b]*h) return a;
else return b;
}
ll s[1<<20];
void update(int l, int r, int idx) {
if (l==r) s[idx]=l;
else {
int mid=(l+r)/2;
update(l,mid,2*idx);
update(mid+1,r,2*idx+1);
s[idx]=check(s[2*idx],s[2*idx+1]);
}
}
void update2(int l, int r, int idx, int x, int y) {
if (l>y || r<x) return;
if (x<=l && y<=r) return;
else {
int mid=(l+r)/2;
update2(l,mid,2*idx,x,y);
update2(mid+1,r,2*idx+1,x,y);
s[idx]=check(s[2*idx],s[2*idx+1]);
}
}
void update3(int l, int r, int idx, int x) {
if (l>x || x>r) return;
if (l==r) return;
else {
int mid=(l+r)/2;
update3(l,mid,2*idx,x);
update3(mid+1,r,2*idx+1,x);
s[idx]=check(s[2*idx],s[2*idx+1]);
}
}
int init(int N, int X[], int Y[]) {
n=N;
for (int i=1; i<=500000; ++i) fen[i]=1;
for (int i=0; i<n; ++i) x[i]=X[i],y[i]=Y[i], update_ms(0,n-1,1,i,x[i]), update_fen(i+1,1,x[i]);
update(0,n-1,1);
return (find_fen(s[1]+1)*y[s[1]])%mod;
}
int updateX(int pos, int val) {
update_fen(pos,x[pos],val);
x[pos]=val;
update_ms(0,n-1,1,pos,val);
update2(0,n-1,1,pos,n-1);
return (find_fen(s[1]+1)*y[s[1]])%mod;
}
int updateY(int pos, int val) {
y[pos]=val;
update3(0,n-1,1,pos);
return (find_fen(s[1]+1)*y[s[1]])%mod;
}
