#include "horses.h"
#include<iostream>
using namespace std;
#pragma GCC optimize("O3,inline")
#define MOD 1000000007
int n;
long long x[600001];
long long aint[2400001];
long long y[600001];
/// Y
struct aint_y{
long long a,poz;
} ainty[2400001];
aint_y combin(aint_y a,aint_y b){
if(a.a>b.a) return a;
return b;
}
void init_aint_y(int nod,int st,int dr){
if(st==dr){
ainty[nod]={y[st],st};
return;
}
int mij=(st+dr)/2;
init_aint_y(2*nod,st,mij);
init_aint_y(2*nod+1,mij+1,dr);
ainty[nod]=combin(ainty[2*nod],ainty[2*nod+1]);
}
void update_y(int nod,int st,int dr,int a){
if(st==dr){
ainty[nod]={y[st],st};
return;
}
int mij=(st+dr)/2;
if(a<=mij) update_y(2*nod,st,mij,a);
else update_y(2*nod+1,mij+1,dr,a);
ainty[nod]=combin(ainty[2*nod],ainty[2*nod+1]);
}
aint_y query_y(int nod,int st,int dr,int a,int b){
if(b<st || dr<a) return {(long long)-1e9,0};
if(a<=st && dr<=b) return ainty[nod];
int mij=(st+dr)/2;
return combin(query_y(2*nod,st,mij,a,b),query_y(2*nod+1,mij+1,dr,a,b));
}
/// X
void init_aint(int nod,int st,int dr){
if(st==dr){
aint[nod]=x[st];
return;
}
int mij=(st+dr)/2;
init_aint(2*nod,st,mij);
init_aint(2*nod+1,mij+1,dr);
aint[nod]=aint[2*nod]*aint[2*nod+1]%MOD;
}
void update(int nod,int st,int dr,int a){
if(st==dr){
aint[nod]=x[st];
return;
}
int mij=(st+dr)/2;
if(a<=mij) update(2*nod,st,mij,a);
else update(2*nod+1,mij+1,dr,a);
aint[nod]=aint[2*nod]*aint[2*nod+1]%MOD;
}
long long query(int nod,int st,int dr,int a,int b){
if(b<st || dr<a) return 1;
if(a<=st && dr<=b) return aint[nod];
int mij=(st+dr)/2;
return query(2*nod,st,mij,a,b)*query(2*nod+1,mij+1,dr,a,b)%MOD;
}
int find_next(int poz){
int dr=poz-1,st=1,rasp=0,mij;
while(st<=dr){
mij=(st+dr)/2;
if(query(1,1,n,mij,n)!=query(1,1,n,poz,n)){
st=mij+1;rasp=mij;
}else dr=mij-1;
}
return rasp;
}
int calc(){
long long ci,prod,i,rasp=1,max1;
ci=n;prod=-1;
for(i=n;i>0;i=find_next(i)){
if(prod>1e9) break;
auto it=query_y(1,1,n,find_next(i)+1,i);
if(it.a>prod){
ci=it.poz;prod=it.a;
}
prod*=x[i];
}
rasp=query(1,1,n,1,ci);
rasp=(rasp*y[ci])%MOD;
return rasp;
}
int init(int N,int X[],int Y[]){
int i;
n=N;
for(i=1;i<=n;i++){
x[i]=X[i-1];
y[i]=Y[i-1];
}
init_aint(1,1,n);
init_aint_y(1,1,n);
return calc();
}
int updateX(int pos,int val){
x[pos+1]=val;
update(1,1,n,pos+1);
return calc();
}
int updateY(int pos,int val){
y[pos+1]=val;
update_y(1,1,n,pos+1);
return calc();
}
