#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N ((int)501*1000)
#define MOD ((int)1e9+7)
int tavan(int x,int y){int res=1;while(y){res=1LL*res*((y%2)?x:1)%MOD;x=1LL*x*x%MOD;y/=2;}return res;}
int n,x[N],y[N];
set <int> s;
int segMul[4*N],segMax[4*N];
void updateMul(int q,int val,int xl=0,int xr=n,int id=1)
{
if(xl==xr-1)
{
segMul[id]=val;
return ;
}
int mid=(xl+xr)/2;
if(q<mid)updateMul(q,val,xl,mid,id*2);
else updateMul(q,val,mid,xr,id*2+1);
segMul[id]=1LL*segMul[id*2]*segMul[id*2+1]%MOD;
return ;
}
void updateMax(int q,int val,int xl=0,int xr=n,int id=1)
{
if(xl==xr-1)
{
segMax[id]=val;
return ;
}
int mid=(xl+xr)/2;
if(q<mid)updateMax(q,val,xl,mid,id*2);
else updateMax(q,val,mid,xr,id*2+1);
segMax[id]=max(segMax[id*2],segMax[id*2+1]);
return ;
}
int queryMul(int q,int xl=0,int xr=n,int id=1)
{
if(xr<=q)return segMul[id];
int mid=(xl+xr)/2,res=queryMul(q,xl,mid,id*2);
if(mid<q)res=1LL*res*queryMul(q,mid,xr,id*2+1)%MOD;
return res;
}
int queryMax(int q,int xl=0,int xr=n,int id=1)
{
if(q<=xl)return segMax[id];
int mid=(xl+xr)/2,res=queryMax(q,mid,xr,id*2+1);
if(q<mid)res=max(res,queryMax(q,xl,mid,id*2));
return res;
}
int solve()
{
vector <int> vec;
auto it=s.end();it--;
ll now=1;
while(1)
{
vec.push_back(*it);
now*=x[*it];
if(now>=1e9+10 || it==s.begin())break;
it--;
}
reverse(vec.begin(),vec.end());
now=1;
ll ans=0;
for(auto u:vec)
{
if(u!=vec[0])now*=x[u];
ans=max(ans,now*queryMax(u));
}
ans%=MOD;
ans*=queryMul(vec[0]+1);ans%=MOD;
return ans;
}
int init(int n2, int X[], int Y[])
{
n=n2;
for(int i=0;i<n;i++)
{
x[i]=X[i];y[i]=Y[i];
if(x[i]>1 || i==0)s.insert(i);
updateMul(i,x[i]);
updateMax(i,y[i]);
}
return solve();
}
int updateX(int pos, int val)
{
x[pos]=val;
if(x[pos]==1 && pos>0)s.erase(pos);
else s.insert(pos);
updateMul(pos,x[pos]);
return solve();
}
int updateY(int pos, int val)
{
y[pos]=val;
updateMax(pos,y[pos]);
return solve();
}
