#include<bits/stdc++.h>
#include "horses.h"
using namespace std;
const int nmax=5e5+42,mod=1e9+7,inf=1e9+42;
int n,x[nmax],y[nmax];
set<int> non_zero;
long long tree_x[4*nmax],tree_y[4*nmax];
void build_x(int node,int l,int r)
{
if(l==r)
{
tree_x[node]=x[l];
return;
}
int av=(l+r)/2;
build_x(node*2,l,av);
build_x(node*2+1,av+1,r);
tree_x[node]=(tree_x[node*2]*tree_x[node*2+1])%mod;
}
void update_x(int node,int l,int r,int pos,int val)
{
if(l==r)
{
tree_x[node]=val;
return;
}
int av=(l+r)/2;
if(pos<=av)update_x(node*2,l,av,pos,val);
else update_x(node*2+1,av+1,r,pos,val);
tree_x[node]=(tree_x[node*2]*tree_x[node*2+1])%mod;
}
int query_x(int node,int l,int r,int lq,int rq)
{
if(l==lq&&r==rq)return tree_x[node];
int av=(l+r)/2;
long long ans=1;
if(lq<=av)ans=ans*query_x(node*2,l,av,lq,min(av,rq))%mod;
if(av<rq)ans=ans*query_x(node*2+1,av+1,r,max(av+1,lq),rq)%mod;
return ans;
}
void build_y(int node,int l,int r)
{
if(l==r)
{
tree_y[node]=y[l];
return;
}
int av=(l+r)/2;
build_y(node*2,l,av);
build_y(node*2+1,av+1,r);
tree_y[node]=max(tree_y[node*2],tree_y[node*2+1]);
}
void update_y(int node,int l,int r,int pos,int val)
{
assert(l<=pos&&pos<=r);
if(l==r)
{
tree_y[node]=val;
return;
}
int av=(l+r)/2;
if(pos<=av)update_y(node*2,l,av,pos,val);
else update_y(node*2+1,av+1,r,pos,val);
tree_y[node]=max(tree_y[node*2],tree_y[node*2+1]);
}
int query_y(int node,int l,int r,int lq,int rq)
{
if(l==lq&&r==rq)return tree_y[node];
int av=(l+r)/2;
int ans=0;
if(lq<=av)ans=max(ans,query_y(node*2,l,av,lq,min(av,rq)));
if(av<rq)ans=max(ans,query_y(node*2+1,av+1,r,max(av+1,lq),rq));
return ans;
}
bool bigger(long long a,long long b,long long c)
{
return a>=(c+b-1)/b;
}
int active[nmax],ind=0;
pair<int,int> slow()
{
double sum=0,maxi=0,now;
int ind=0;
for(int i=0;i<n;i++)
{
sum=sum+log10(1.0*x[i]);
now=sum+log10(1.0*y[i]);
if(now>maxi+1.0/1e9)
{
maxi=now;
ind=i;
}
}
long long res=y[ind];
for(int i=0;i<=ind;i++)
{
res=res*x[i]%mod;
}
return {res,ind};
}
void test(long long a,long long b,long long &c,long long &d)
{
double p=log10(1.0*a)+log10(1.0*b),q=log10(1.0*c)+log10(1.0*d);
if(p>q+1.0/1e9)
{
c=a;
d=b;
}
}
int query()
{
if(non_zero.size()==0)return query_y(1,0,n-1,0,n-1);
long long prod=1,maxi=1;
int last=n,pos=-1;
ind=0;
for(auto k:non_zero)
{
pos=-k;
active[++ind]=pos;
prod=prod*x[pos];
if(prod>inf)break;
}
reverse(active+1,active+ind+1);
//cout<<"active: ";for(int i=1;i<=ind;i++)cout<<active[i]<<" ";cout<<endl;
prod=1;
long long p1,b1=1,b2=1;
for(int i=1;i<ind;i++)
{
prod=prod*x[active[i]];
//cout<<"q "<<query_y(1,0,n-1,active[i],active[i+1]-1)<<endl;
p1=query_y(1,0,n-1,active[i],active[i+1]-1);
test(prod,p1,b1,b2);
}
if(ind==non_zero.size())
{
if(active[1]!=0)maxi=max(maxi,1LL*query_y(1,0,n-1,0,active[1]-1));
}
test(maxi,1,b1,b2);
//cout<<maxi<<endl;
long long mult=1;
if(ind!=non_zero.size())mult=query_x(1,0,n-1,0,active[1]-1);
long long a=prod*x[active[ind]];
long long b=query_y(1,0,n-1,active[ind],n-1);
test(a,b,b1,b2);
long long ret=mult%mod*(b1%mod)%mod*(b2%mod)%mod;
/*
if(n<=1000)
{
if(ret!=slow().first)
{
cout<<a<<" "<<b<<" "<<maxi<<" "<<mult<<endl;
cout<<"active: ";for(int i=1;i<=ind;i++)cout<<active[i]<<" ";cout<<endl;
cout<<ret<<endl;
for(int i=0;i<n;i++)cout<<x[i]<<" ";cout<<endl;
cout<<endl;
for(int i=0;i<n;i++)cout<<y[i]<<" ";cout<<endl;
cout<<slow().first<<" "<<slow().second<<" "<<x[slow().second]<<" "<<y[slow().second]<<endl;
system("pause");
if(bigger(a,b,maxi))
{
assert(slow().second>=active[1]);
while(1);
}
else assert(0==1);
}
}
*/
return ret;
}
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];
for(int i=0;i<N;i++)
if(x[i]!=1)
{
non_zero.insert(-i);
}
build_x(1,0,n-1);
build_y(1,0,n-1);
return query();
}
int updateX(int pos,int val)
{
if(x[pos]!=1)non_zero.erase(-pos);
x[pos]=val;
if(x[pos]!=1)non_zero.insert(-pos);
update_x(1,0,n-1,pos,val);
return query();
}
int updateY(int pos,int val)
{
y[pos]=val;
update_y(1,0,n-1,pos,val);
return query();
}
