#include "horses.h"
#include <bits/stdc++.h>
#define MOD 1000000007
typedef long long ll;
using namespace std;
int xx[500005],yy[500005];
long long y[500005],x[500005],rightt[500005],leftt[500005];
long long pro[5000000],n,mx[5000000];
set<pair<ll,ll> >s;
void build1(long long id,long long l,long long r){
if(l==r){
mx[id]=y[l];
return;
}
ll m=(l+r)>>1;
build1(id*2,l,m);
build1(id*2+1,m+1,r);
mx[id]=max(mx[id*2],mx[id*2+1]);
}
void build(long long id,long long l,long long r){
if(l==r){
pro[id]=x[l];
return;
}
long long m=(l+r)>>1;
build(id*2,l,m);
build(id*2+1,m+1,r);
pro[id]=pro[id*2]*pro[id*2+1];
if(pro[id]>=MOD) pro[id]%=MOD;
}
long long query(long long id,long long l,long long r,long long L,long long R){
if(R<L) return 1;
if(r<L || R<l) return 1;
if(L<=l && r<=R) return pro[id];
long long m=(l+r)>>1;
return (query(id*2,l,m,L,R)*query(id*2+1,m+1,r,L,R))%MOD;
}
long long query1(ll id,ll l,ll r,ll L,ll R){
if(R<l || r<L) return 0;
if(L<=l && r<=R) return mx[id];
ll m=(l+r)>>1;
return max(query1(id*2,l,m,L,R),query1(id*2+1,m+1,r,L,R));
}
void update(ll id,ll l,ll r,ll d,ll e){
if(l==r){
pro[id]=e;
return;
}
ll m=(l+r)>>1;
if(m>=d) update(id*2,l,m,d,e);
else update(id*2+1,m+1,r,d,e);
pro[id]=pro[id*2]*pro[id*2+1];
if(pro[id]>=MOD) pro[id]%=MOD;
}
void update1(ll id,ll l,ll r,ll d,ll e){
if(l==r){
mx[id]=e;
return;
}
ll m=(l+r)>>1;
if(m>=d) update1(id*2,l,m,d,e);
else update1(id*2+1,m+1,r,d,e);
mx[id]=max(mx[id*2],mx[id*2+1]);
}
int init(int N,int X[],int Y[]){
s.insert({-1,-1});
memset(leftt,-1,sizeof(leftt));
memset(rightt,-1,sizeof(rightt));
n=(long long)N;
for(long long i=0;i<n;i++){
y[i]=(long long)Y[i];
x[i]=(long long)X[i];
}
build(1,0,n-1);
build1(1,0,n-1);
bool flag=0;
long long l;
for(long long i=0;i<n;i++){
if(x[i]==1 && flag==0){
flag=1;
l=i;
}
if(x[i]!=1 && flag==1){
flag=0;
s.insert({l,i-1});
rightt[l]=i-1;
leftt[i-1]=l;
}
}
if(flag==1){
rightt[l]=n-1;
leftt[n-1]=l;
s.insert({l,n-1});
}
long long c=y[n-1];
pair<long double,ll>p={0,-1};
for(ll i=n-1;i>=0;i--){
ll val=y[i];
if(leftt[i]!=-1){
i=leftt[i];
val=query1(1,0,n-1,i,rightt[i]);
}
// cout << (long double)(val)/(long double)(c) << ' ' << i << '\n';
p=max(p,{(long double)(val)/(long double)(c),i});
c*=x[i];
if(c>=1000000000) break;
}
ll ans=query(1,0,n-1,0,p.second);
ll id=p.second,val=y[id];
if(rightt[id]!=-1) val=query1(1,0,n-1,id,rightt[id]);
return (ans*val)%MOD;
}
int updateX(int pos, int val){
update(1,0,n-1,pos,val);
x[pos]=val;
if(val==1){
pair<ll,ll>temp={pos,1000000000};
auto it=s.lower_bound(temp);
--it;
if(it->first>pos || pos>it->second){
leftt[pos]=pos;
rightt[pos]=pos;
s.insert({leftt[pos],rightt[pos]});
if(pos>0 && leftt[pos-1]!=-1){
rightt[leftt[pos-1]]=rightt[pos];
leftt[rightt[pos]]=leftt[pos-1];
s.erase({leftt[pos-1],pos-1});
s.erase({pos,rightt[pos]});
s.insert({leftt[pos-1],rightt[pos]});
rightt[pos]=-1;
leftt[pos-1]=-1;
}
if(pos<(n-1) && rightt[pos+1]!=-1){
rightt[leftt[pos]]=rightt[pos+1];
leftt[rightt[pos+1]]=leftt[pos];
s.erase({leftt[pos],pos});
s.erase({pos+1,rightt[pos+1]});
s.insert({leftt[pos],rightt[pos+1]});
rightt[pos+1]=-1;
leftt[pos]=-1;
}
}
}
else{
pair<ll,ll>temp={pos,1000000000};
auto it=s.lower_bound(temp);
--it;
if(it->first<=pos && pos<=it->second){
ll st=it->first;
ll en=it->second;
s.erase(it);
leftt[en]=-1;
rightt[st]=-1;
if(st!=pos){
rightt[st]=pos-1;
leftt[pos-1]=st;
s.insert({st,pos-1});
}
if(en!=pos){
leftt[en]=pos+1;
rightt[pos+1]=en;
s.insert({pos+1,en});
}
}
}
long long c=y[n-1];
pair<long double,ll>p={0,-1};
for(ll i=n-1;i>=0;i--){
ll value=y[i];
if(leftt[i]!=-1){
i=leftt[i];
value=query1(1,0,n-1,i,rightt[i]);
}
p=max(p,{(long double)(value)/(long double)(c),i});
c*=x[i];
if(c>=1000000000) break;
}
ll ans=query(1,0,n-1,0,p.second);
ll id=p.second,value=y[id];
if(rightt[id]!=-1) value=query1(1,0,n-1,id,rightt[id]);
return (ans*value)%MOD;
}
int updateY(int pos, int val) {
update1(1,0,n-1,pos,val);
y[pos]=val;
long long c=y[n-1];
pair<long double,ll>p={0,-1};
for(ll i=n-1;i>=0;i--){
ll value=y[i];
if(leftt[i]!=-1){
i=leftt[i];
value=query1(1,0,n-1,i,rightt[i]);
}
p=max(p,{(long double)(value)/(long double)(c),i});
c*=x[i];
if(c>=1000000000) break;
}
ll ans=query(1,0,n-1,0,p.second);
ll id=p.second,value=y[id];
if(rightt[id]!=-1) value=query1(1,0,n-1,id,rightt[id]);
return (ans*value)%MOD;
}
