#include<bits/stdc++.h>
using namespace std;
#define ll long long
const __int128 MOD=1e9+7;
// TODO: global variables can be declared here
struct SEG{
vector<ll>seg,arr;
void init(ll n){
seg.resize(4*n+5),arr.resize(n+5);
}
void build(ll l, ll r, ll id){
if(l==r){
seg[id]=arr[l];
}
else{
ll mid=(l+r)>>1;
build(l,mid,id*2),build(mid+1,r,id*2+1);
seg[id]=max(seg[id*2],seg[id*2+1]);
}
}
void upd(ll ul, ll l, ll r, ll val, ll id){
if(l==r){
seg[id]=val;
}
else{
ll mid=(l+r)>>1;
if(ul<=mid)upd(ul,l,mid,val,id*2);
else upd(ul,mid+1,r,val,id*2+1);
seg[id]=max(seg[id*2],seg[id*2+1]);
}
}
ll qry(ll ql, ll qr, ll l, ll r, ll id){
if(l>qr||r<ql){
return -1e18;
}
if(l>=ql&&r<=qr)return seg[id];
ll mid=(l+r)>>1;
return max(qry(ql,qr,l,mid,id*2),qry(ql,qr,mid+1,r,id*2+1));
}
}st;
struct MULTIPLICATION{
vector<ll>seg,arr;
void init(ll n){
seg.resize(4*n+5),arr.resize(n+5);
}
void build(ll l, ll r, ll id){
if(l==r){
seg[id]=arr[l]%MOD;
}
else{
ll mid=(l+r)>>1;
build(l,mid,id*2),build(mid+1,r,id*2+1);
seg[id]=seg[id*2]*seg[id*2+1];
seg[id]%=MOD;
}
}
void upd(ll ul, ll l, ll r, ll val, ll id){
if(l==r){
seg[id]=val;
seg[id]%=MOD;
}
else{
ll mid=(l+r)>>1;
if(ul<=mid)upd(ul,l,mid,val,id*2);
else upd(ul,mid+1,r,val,id*2+1);
seg[id]=seg[id*2]*seg[id*2+1];
seg[id]%=MOD;
}
}
ll qry(ll ql, ll qr, ll l, ll r, ll id){
if(l>qr||r<ql){
return 1;
}
if(l>=ql&&r<=qr)return seg[id];
ll mid=(l+r)>>1;
return (qry(ql,qr,l,mid,id*2)*qry(ql,qr,mid+1,r,id*2+1)%MOD);
}
}mul;
vector<ll>qry;
set<ll>ms;
vector<ll>x,y;
ll n;
ll func(){
__int128 m=1;
for(ll u: ms){
if(m>MOD){break;}
m*=x[-u];
qry.push_back(-u);
}
ll ans; __int128 maxi=-1e18;
bool ok=0;
if(m<=MOD){
ans=st.qry(1,n,1,n,1);
ok=1;
}
reverse(qry.begin(),qry.end());
m=1;
for(int i=0;i<qry.size();i++){
m*=x[qry[i]];
__int128 mu;
if(i==qry.size()-1)mu=st.qry(qry[i],n,1,n,1);
else mu=st.qry(qry[i],qry[i+1]-1,1,n,1);
if(mu*m>maxi){
maxi=mu*m;
ll store=mu%MOD;
if(!ok){
ans=mul.qry(1,qry[i],1,n,1)*store%MOD;
}
else{
ans=max(ans,mul.qry(1,qry[i],1,n,1)*store);
}
}
}
qry.clear();
return ans%MOD;
}
int init(int N, int X[], int Y[]) {
// TODO: implementation
n=N;
st.init(N);mul.init(n);
x.push_back(0),y.push_back(0);
for(int i=0;i<n;i++){
x.push_back(X[i]);
y.push_back(Y[i]);
}
for(int i=1;i<=n;i++){
st.arr[i]=y[i];
mul.arr[i]=x[i];
}
st.build(1,n,1),mul.build(1,n,1);
for(int i=1;i<=n;i++){
if(x[i]!=1){
ms.insert(-i);
}
}
return func();
}
int updateX(int pos, int val) {
// TODO: implementation
pos++;
if(x[pos]!=1){
ms.erase(-pos);
}
x[pos]=val;
mul.upd(pos,1,n,val,1);
if(x[pos]!=1)ms.insert(-pos);
return func();
}
int updateY(int pos, int val) {
// TODO: implementation
pos++;
y[pos]=val;
st.upd(pos,1,n,val,1);
return func();
}
