#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD=1e9+7;
const int K=5e5+10;
const int M=1<<20;
int n;
ll x[K],y[K];
ll mpow(ll base,ll po){
ll ret=1,mult=base;
while(po){
if(po%2) ret=(ret*mult)%MOD;
po/=2;
mult=(mult*mult)%MOD;
}
return ret;
}
ll mult(ll a,ll b){return (a*b)%MOD;}
ll inv(ll a){return mpow(a,MOD-2);}
struct stree{
vector<long long> s,lz,arr;
void init(){
s.resize(M),lz.resize(M,1),arr.resize(M);
}
void deb(){
for(int i=0;i<n;i++){
int tmp=query(0,n-1,1,i,i);
cout<<tmp <<" ";
}
cout<<"\n";
}
void pushlz(int l,int r,int idx){
if(lz[idx]==1) return;
s[idx]=mult(s[idx],lz[idx]);
if(l!=r) lz[idx*2]=mult(lz[idx*2],lz[idx]),lz[idx*2+1]=mult(lz[idx*2+1],lz[idx]);
lz[idx]=1;
}
void build(int l,int r,int idx){
if(l==r){
s[idx]=arr[l];
return;
}
int m=(l+r)/2;
build(l,m,idx*2);
build(m+1,r,idx*2+1);
s[idx]=max(s[idx*2],s[idx*2+1]);
}
void update(int l,int r,int idx,int a,int b,int val){
pushlz(l,r,idx);
if(a>r || b<l) return;
if(a<=l && b>=r){
lz[idx]=mult(lz[idx],val);
pushlz(l,r,idx);
return;
}
int m=(l+r)/2;
update(l,m,idx*2,a,b,val);
update(m+1,r,idx*2+1,a,b,val);
s[idx]=max(s[idx*2],s[idx*2+1]);
}
ll query(int l,int r,int idx,int a,int b){
pushlz(l,r,idx);
if(a>r || b<l) return INT_MIN;
if(a<=l && b>=r) return s[idx];
int m=(l+r)/2;
return max(query(l,m,idx*2,a,b),query(m+1,r,idx*2+1,a,b));
}
}st;
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];
long long ac=1;
st.init();
for(int i=0;i<N;i++){
ac=mult(ac,x[i]);
st.arr[i]=mult(ac,y[i]);
}
st.build(0,N-1,1);
//st.deb();
ll tmp=st.query(0,N-1,1,0,N-1);
return tmp;
}
int updateX(int pos, int val) {
st.update(0,n-1,1,pos,n-1,inv(x[pos]));
//st.deb();
st.update(0,n-1,1,pos,n-1,val);
//st.deb();
x[pos]=val;
//st.deb();
ll tmp=st.query(0,n-1,1,0,n-1);
return tmp;
}
int updateY(int pos, int val) {
st.update(0,n-1,1,pos,pos,inv(y[pos]));
//st.deb();
st.update(0,n-1,1,pos,pos,val);
//st.deb();
y[pos]=val;
//st.deb();
ll tmp=st.query(0,n-1,1,0,n-1);
return tmp;
}
