#include "horses.h"
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll i,has=0,hz=1,x[505050],y[505050],PS=1,mo=1000000007,K,n;
ll ST[2020202],ST2[2020202],te,a[505050],ST3[2020202];
void upd(ll aa,ll bb,ll cc,ll dd,ll ee)
{
if(aa==bb)
ST[ee]=dd;
else
{
ll ce=(aa+bb)/2;
if(cc<=ce)upd(aa,ce,cc,dd,ee*2);
else upd(ce+1,bb,cc,dd,ee*2+1);
ST[ee]=(ST[ee*2]*ST[ee*2+1])%mo;
}
}
void upd2(ll aa,ll bb,ll cc,ll dd,ll ee)
{
if(aa==bb)
ST2[ee]=dd;
else
{
ll ce=(aa+bb)/2;
if(cc<=ce)upd2(aa,ce,cc,dd,ee*2);
else upd2(ce+1,bb,cc,dd,ee*2+1);
ST2[ee]=(ST2[ee*2]+ST2[ee*2+1]);
}
}
void upd3(ll aa,ll bb,ll cc,ll dd,ll ee)
{
if(aa==bb)
ST3[ee]=dd;
else
{
ll ce=(aa+bb)/2;
if(cc<=ce)upd3(aa,ce,cc,dd,ee*2);
else upd3(ce+1,bb,cc,dd,ee*2+1);
ST3[ee]=max(ST3[ee*2],ST3[ee*2+1]);
}
}
ll cari(ll aa,ll bb,ll cc,ll ee)
{
if(aa==bb)
{
a[++te]=aa;
}
else
{
ll ce=(aa+bb)/2;
if(ST2[ee*2+1]==0)
cari(aa,ce,cc,ee*2);
else
{
if(cc<=ST2[ee*2+1])cari(ce+1,bb,cc,ee*2+1);
else
{
cari(aa,ce,cc-ST2[ee*2+1],ee*2);
cari(ce+1,bb,ST2[ee*2+1],ee*2+1);
}
}
}
}
ll que(ll aa,ll bb,ll cc,ll dd,ll ee)
{
if(bb<cc||dd<aa)return 1LL;
else if(cc<=aa&&bb<=dd)return ST[ee];
else
{
ll ce=(aa+bb)/2;
return (que(aa,ce,cc,dd,ee*2)*que(ce+1,bb,cc,dd,ee*2+1))%mo;
}
}
ll que3(ll aa,ll bb,ll cc,ll dd,ll ee)
{
if(bb<cc||dd<aa)return 0LL;
else if(cc<=aa&&bb<=dd)return ST3[ee];
else
{
ll ce=(aa+bb)/2;
return max(que3(aa,ce,cc,dd,ee*2),que3(ce+1,bb,cc,dd,ee*2+1));
}
}
ll powo(ll aa,ll bb)
{
if(bb==0)return 1LL;
else
{
ll tem=powo(aa,bb/2);
tem=(tem*tem)%mo;
if(bb%2==1)tem=(tem*aa)%mo;
return tem;
}
}
ll com(ll aa,ll bb)
{
return (que(0,n-1,0,aa,1)*bb)%mo;
}
ll jaw()
{
te=0;
//memset(a,-1,sizeof(a));
cari(0,n-1,min(32LL,ST2[1]),1);
// sort(a+1)
ll opt=a[te],hz=y[a[te]],ii,Z=x[a[te]];
//for(ii=1;ii<=te;ii++) cout<<ii<<" "<<a[ii]<<"\n";
for(ii=te-1;ii>=1;ii--)
{
if(Z>1000000000)return com(opt,hz);
//cout<<que3(0,n-1,a[ii],a[ii+1]-1,1)<<"\n";
if(que3(0,n-1,a[ii],a[ii+1]-1,1)>Z*hz)
{
opt=a[ii];
hz=que3(0,n-1,a[ii],a[ii+1]-1,1);
Z=1;
}
Z*=x[a[ii]];
}
return com(opt,hz);
}
int init(int N, int X[], int Y[])
{
n=N;
for(i=0;i<N;i++)x[i]=X[i];
for(i=0;i<N;i++)upd(0,n-1,i,x[i],1);
for(i=0;i<N;i++)upd2(0,n-1,i,((x[i]>1)||(i==0||i==(n-1))),1);
for(i=0;i<N;i++)y[i]=Y[i];
for(i=0;i<N;i++)upd3(0,n-1,i,y[i],1);
//K=max(0LL,n-32LL);
K=0;
return jaw();
}
int updateX(int pos, int val)
{
upd(0,n-1,pos,val,1);
upd2(0,n-1,pos,((val>1)||(pos==0||pos==(n-1))),1);
x[pos]=val;
return jaw();
}
int updateY(int pos, int val)
{
y[pos]=val;
upd3(0,n-1,pos,val,1);
return jaw();
}
