#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
typedef long long ll;
const ll MX=1e9,MX_N=5e5,MOD=1e9+7;
const ll SZ=(1<<(int)ceil(log2(MX_N))+1);
int N;
ll X[MX_N+1],Y[MX_N+1],XTree[SZ],YTree[SZ];
priority_queue<int> Q;
vector<int> Idx;
ll mul_update(ll *tree,int s,int e,int idx,ll v,int n){
if (idx<s||e<idx)
return tree[n];
if (s==e)
return tree[n]=v;
int m=(s+e)>>1;
return tree[n]=mul_update(tree,s,m,idx,v,n<<1)*mul_update(tree,m+1,e,idx,v,n<<1|1)%MOD;
}
ll mul_query(ll *tree,int s,int e,int l,int r,int n){
if (r<s||e<l)
return 1;
if (l<=s&&e<=r)
return tree[n];
int m=(s+e)>>1;
return mul_query(tree,s,m,l,r,n<<1)*mul_query(tree,m+1,e,l,r,n<<1|1)%MOD;
}
ll max_update(ll *tree,int s,int e,int idx,ll v,int n){
if (idx<s||e<idx)
return tree[n];
if (s==e)
return tree[n]=v;
int m=(s+e)>>1;
return tree[n]=max(max_update(tree,s,m,idx,v,n<<1),max_update(tree,m+1,e,idx,v,n<<1|1));
}
ll max_query(ll *tree,int s,int e,int l,int r,int n){
if (r<s||e<l)
return 0;
if (l<=s&&e<=r)
return tree[n];
int m=(s+e)>>1;
return max(max_query(tree,s,m,l,r,n<<1),max_query(tree,m+1,e,l,r,n<<1|1));
}
int ans(){
Idx.clear();
Idx.push_back(N);
ll mul=1;
while (!Q.empty()){
int t=Q.top();
Q.pop();
Idx.push_back(t);
mul*=X[t];
if (mul>MX)
break;
}
if (mul<=MX)
Idx.push_back(0);
mul=1;
ll max_x=X[Idx.back()],max_y=0;
int idx;
for (int i=Idx.size()-1; i>0; i--){
mul*=X[Idx[i]];
ll t=max_query(YTree,0,N-1,Idx[i],Idx[i-1]-1,1);
if (max_y<mul/max_x*t){
max_x=mul;
max_y=t;
idx=Idx[i-1]-1;
}
}
for (int i:Idx){
if (X[i]>1)
Q.push(i);
}
return mul_query(XTree,0,N-1,0,idx,1)*max_y%MOD;
}
int init(int n, int x[], int y[]){
N=n;
for (int i=0; i<N; i++){
X[i]=x[i];
if (X[i]>1)
Q.push(i);
mul_update(XTree,0,N-1,i,X[i],1);
Y[i]=y[i];
max_update(YTree,0,N-1,i,Y[i],1);
}
return ans();
}
int updateX(int pos, int val) {
if (val>1&&X[pos]==1)
Q.push(pos);
X[pos]=val;
mul_update(XTree,0,N-1,pos,val,1);
return ans();
}
int updateY(int pos, int val) {
Y[pos]=val;
max_update(YTree,0,N-1,pos,val,1);
return ans();
}
