#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 1e9+7;
const ll INF = 1e9;
int n;
set<int> s;
int aint[1100000];
void upd(int nod, int st, int dr, int poz, int newv)
{
if(st==dr)
{
aint[nod] = newv;
return;
}
int mij=(st+dr)/2;
if(poz<=mij) upd(nod*2,st,mij,poz,newv);
else upd(nod*2+1,mij+1,dr,poz,newv);
aint[nod] = max(aint[nod*2], aint[nod*2+1]);
}
int qry(int nod, int st, int dr, int le, int ri)
{
if(le>ri)
return 0;
if(le==st && dr==ri)
return aint[nod];
int mij=(st+dr)/2;
return max(qry(nod*2,st,mij,le,min(mij,ri)), qry(nod*2+1,mij+1,dr,max(mij+1,le),ri));
}
ll put(ll a, int exp)
{
if(exp==0)
return 1;
if(exp%2==0)
return put(a*a%MOD,exp/2);
else
return put(a*a%MOD,exp/2)*a%MOD;
}
ll X[500005],Y[500005];
ll tot;
long long solve()
{
s.insert(0);
auto it = s.end();
vector<int> pozs;
ll prod=1;
while(it!=s.begin() && prod<INF)
{
it--;
//if(prod * X[*it] > INF) break;
pozs.push_back(*it);
prod *= X[pozs.back()];
}
reverse(pozs.begin(),pozs.end());
ll pref=1;
ll mxm=0;
for(int i:pozs)
{
pref *= X[i];
mxm = max(mxm, pref * qry(1,0,n-1,i,n-1));
}
return mxm * tot%MOD * put(prod,MOD-2)%MOD;
}
int init(int N, int copX[], int copY[])
{
for(int i=0;i<N;i++)
{
X[i] = copX[i];
Y[i] = copY[i];
}
n=N;
tot=1;
for(int i=0;i<N;i++)
{
if(X[i]>1) s.insert(i);
upd(1,0,n-1,i,Y[i]);
tot = tot*X[i]%MOD;
}
return solve();
}
int updateX(int pos, int val)
{
tot = tot * put(X[pos],MOD-2)%MOD * val%MOD;
X[pos] = val;
s.erase(pos);
if(val>1) s.insert(pos);
return solve();
}
int updateY(int pos, int val)
{
Y[pos] = val;
upd(1,0,n-1,pos,val);
return solve();
}
