#include "horses.h"
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ld long double
#define mp make_pair
#define F first
#define S second
#define pii pair<ll,ll>
using namespace :: std;
const ll maxn=5e5+500;
const ll inf=1e9+6;
const ll mod=1e9+7;
ll modizarb(long long a,long long b){return (a*b)%mod;}
ll y[maxn];
ll seg[maxn*4];
void bild(ll l,ll r,ll node){
if(l+1==r){
seg[node]=y[l];
return;
}
ll mid=(l+r)/2;
bild(l,mid,2*node);
bild(mid,r,2*node+1);
seg[node]=max(seg[2*node],seg[2*node+1]);
}
void update(ll l,ll r,ll node,ll pos){
if(l+1==r){
seg[node]=y[l];
return;
}
ll mid=(l+r)/2;
if(pos<mid)
update(l,mid,2*node,pos);
else
update(mid,r,2*node+1,pos);
seg[node]=max(seg[2*node],seg[2*node+1]);
}
ll findMx(ll l,ll r,ll L,ll R,ll node){
if(l<=L && R<=r){
return seg[node];
}
if(r<=L || R<=l){
return 0;
}
ll mid=(L+R)/2;
return max(findMx(l,r,L,mid,2*node),findMx(l,r,mid,R,2*node+1));
}
set<ll> st;
ll x[maxn];
ll rx[maxn];
ll n,Z;
ll poww(ll a,ll b){
ll ans=1;
while(b){
if(b&1){
ans=(ans*a)%mod;
}
b>>=1;
a=(a*a)%mod;
}
return ans;
}
ll findAns(){
auto it=st.end();
ll last=n;
ll ans=0;
ll t=Z;
bool br=0;
while(it!=st.begin()){
it--;
ll v=(*it);
ll yy=findMx(v,last,0,n,1);
ans=max(ans,yy);
if(ans*x[v]>inf){
br=1;
break;
}
ans*=x[v];
t=modizarb(t,rx[v]);
last=v;
}
if(!br){
ll v=0;
ll yy=findMx(v,last,0,n,1);
ans=max(ans,yy);
}
return modizarb(ans,t);
}
int init(int N, int X[], int Y[]){
n=N;
Z=1;
for(ll i=0;i<n;i++){
x[i]=X[i];
Z=modizarb(Z,X[i]);
rx[i]=poww(x[i],mod-2);
y[i]=Y[i];
if(x[i]!=1)st.insert(i);
}
bild(0,n,1);
return findAns();
}
int updateX(int pos, int val) {
Z=modizarb(Z,rx[pos]);
if(x[pos]!=1 && val==1){
st.erase(pos);
}
if(x[pos]==1 && val!=1){
st.insert(pos);
}
x[pos]=val;
Z=modizarb(Z,val);
rx[pos]=poww(x[pos],mod-2);
return findAns();
}
int updateY(int pos, int val){
y[pos]=val;
update(0,n,1,pos);
return findAns();
}
