#include "horses.h"
#define x first
#define y second
#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb push_back
#define ll long long
#define vi vector<int>
#define vl vector<ll>
using namespace std;
const int MOD=1000000007,N=500010,M=1<<19;
const char en='\n';
const ll LLINF=1ll<<60;
int n,x[N],y[N];
set<int> le;
int segP[M*2+10],segM[M*2+10];
pii v[N];
bool debug=0;
void updP(int i,int x)
{
i+=M;
segP[i]=x;
for (i/=2;i;i/=2) segP[i]=segP[i*2]*1ll*segP[i*2+1]%MOD;
}
void updM(int i,int x)
{
i+=M;
segM[i]=x;
for (i/=2;i;i/=2) segM[i]=max(segM[i*2],segM[i*2+1]);
}
int getP(int l,int r,int lo=0,int hi=M,int i=1)
{
if (lo>=l && hi<=r) return segP[i];
if (lo>=r || hi<=l) return 1;
int mid=(lo+hi)/2;
return getP(l,r,lo,mid,i*2)*1ll*getP(l,r,mid,hi,i*2+1)%MOD;
}
int getM(int l,int r,int lo=0,int hi=M,int i=1)
{
if (lo>=l && hi<=r) return segM[i];
if (lo>=r || hi<=l) return 0;
int mid=(lo+hi)/2;
return max(getM(l,r,lo,mid,i*2),getM(l,r,mid,hi,i*2+1));
}
#define lll __int128
int getSol()
{
ll pro=1;
int e,le;
for (e=n-1;pro<=MOD-7 && e>=0;e=v[e].x) pro*=x[e],le=e;
if (debug) cout<<"moram do "<<e<<", umnozak je "<<pro<<endl;
lll ma=0;
lll jedan=1;
int f,lf;
for (f=n-1;pro && f>=0;f=v[f].x)
{
ma=max(ma,pro*jedan*y[f]);
if (debug) cout<<"na "<<f<<" je pro="<<pro<<", y="<<y[f]<<", le="<<le<<endl;
pro/=x[f];
if (debug) cout<<"od "<<f<<" do "<<v[f].x<<" je pro="<<pro<<", max_y="<<v[f].y<<", ma="<<(ll)(ma%MOD)<<endl;
ma=max(ma,pro*jedan*v[f].y);
lf=f;
}
return (ma%MOD)*getP(0,le)%MOD;
}
int init(int N, int X[], int Y[]) {
n=N;
for (int i=0;i<n;++i) x[i]=X[i],y[i]=Y[i],segP[i+M]=x[i],segM[i+M]=y[i];
for (int i=n;i<M;++i) segP[i+M]=1;
for (int i=M-1;i>0;--i) segP[i]=segP[i*2]*1ll*segP[i*2+1]%MOD,segM[i]=max(segM[i*2],segM[i*2+1]);
if (debug) cout<<"pola inita gotovo"<<endl;
for (int i=n-1;i>=0;)
{
le.insert(i);
int j=i-1,ma=0;
while (j>=0 && x[j]==1) ma=max(ma,y[j]),--j;
v[i]={j,ma};
if (debug) cout<<"od "<<i<<" do "<<j<<" sa maks="<<ma<<endl;
i=j;
}
//if (debug) cout<<"rjesenje inita je "<<getSol()<<endl;
return getSol();
}
int updateX(int pos, int val) {
int sxp=x[pos];
x[pos]=val;
updP(pos,val);
if (sxp==1)
{
if (val==1 || pos==n-1) return getSol();
int z=*le.upper_bound(pos);
int et=v[z].x;
v[z]={pos,getM(pos+1,z)};
v[pos]={et,getM(et+1,pos)};
le.insert(pos);
if (debug) for (int i=n-1;i>=0;i=v[i].x) cout<<"od "<<i<<" do "<<v[i].x<<" sa maks="<<v[i].y<<endl;
return getSol();
}
else
{
if (val!=1 || pos==n-1)
{
return getSol();
}
int z=*le.upper_bound(pos);
v[z]={v[pos].x,getM(v[pos].x+1,z)};
v[pos]={0,0};
le.erase(le.find(pos));
return getSol();
}
return getSol();
}
int updateY(int pos, int val) {
y[pos]=val;
updM(pos,val);
if (pos!=n-1)
{
int z=*le.upper_bound(pos);
v[z].y=getM(v[z].x+1,z);
}
return getSol();
}
