#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
const int MOD = 1000000007;
typedef pair<long double,ll> ii;
ll x[500005],y[500005];
int n;
ii st[2000005],A[500005],lazy[2000005];
void mod(ll& a){
if(a>=MOD)a%=MOD;
}
int binpow(ll a,ll b){
if(!b)return 1;
ll res=binpow(a,b/2);
res*=res;
mod(res);
if(b&1)res*=a,mod(res);
return (int)res;
}
void build(int node,int l,int r){
lazy[node]={0,1};
if(l==r){
st[node]={A[l].fi+log(y[l]),A[l].se*y[l]};
mod(st[node].se);
return;
}
int med=(l+r)>>1;
build(node*2,l,med),build(node*2+1,med+1,r);
st[node]=max(st[node*2],st[node*2+1]);
}
void prop(int node,int l,int r){
if(lazy[node].fi){
st[node].fi+=lazy[node].fi;
st[node].se*=lazy[node].se;
mod(st[node].se);
if(l!=r){
lazy[node*2].fi+=lazy[node].fi;
lazy[node*2+1].fi+=lazy[node].fi;
lazy[node*2].se*=lazy[node].se;
lazy[node*2+1].se*=lazy[node].se;
mod(lazy[node*2].se),mod(lazy[node*2+1].se);
}
lazy[node]={0,1};
}
}
void updx(int node,int l,int r,int i,int j,ii val){
prop(node,l,r);
if(l>j || r<i)
return;
if(l>=i && r<=j){
lazy[node]=val;
prop(node,l,r);
return;
}
int med=(l+r)>>1;
updx(node*2,l,med,i,j,val),updx(node*2+1,med+1,r,i,j,val);
st[node]=max(st[node*2],st[node*2+1]);
}
void updy(int node,int l,int r,int idx,ii val){
prop(node,l,r);
if(l>idx || r<idx)
return;
if(l==r){
st[node].fi+=val.fi;
st[node].se*=val.se;
mod(st[node].se);
return;
}
int med=(l+r)>>1;
updy(node*2,l,med,idx,val),updy(node*2+1,med+1,r,idx,val);
st[node]=max(st[node*2],st[node*2+1]);
}
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];
A[i].fi=log(x[i]);
if(i)A[i].fi+=A[i-1].fi;
A[i].se=x[i];
if(i)A[i].se*=A[i-1].se,mod(A[i].se);
}
build(1,0,n-1);
return (int)(st[1].se);
}
int updateX(int pos, int val) {
ii h={-log(x[pos]),binpow(x[pos],MOD-2)};
x[pos]=val;
h.fi+=log(val),h.se*=val;
mod(h.se);
updx(1,0,n-1,pos,n-1,h);
prop(1,0,n-1);
return (int)st[1].se;
}
int updateY(int pos, int val) {
ii h={-log(y[pos]),binpow(y[pos],MOD-2)};
y[pos]=val;
h.fi+=log(val),h.se*=val;
mod(h.se);
updy(1,0,n-1,pos,h);
prop(1,0,n-1);
return (int)st[1].se;
}
