#include<iostream>
#include "horses.h"
#define DIM 500005
#define mod 1000000007
using namespace std;
static int n;
static int x[DIM], y[DIM], lst[DIM];
struct str{
int prod, xm, ym;
};
static str aint[4 * DIM], aux;
static void build(int nod, int st, int dr){
if(st == dr){
aint[nod] = {x[st], x[st], y[st]};
}
else{
int mid = (st + dr) / 2;
build(2 * nod, st, mid);
build(2 * nod + 1, mid + 1, dr);
aint[nod].prod = aint[2 * nod].prod * 1LL * aint[2 * nod + 1].prod % mod;
aint[nod].xm = max(aint[2 * nod].xm, aint[2 * nod + 1].xm);
aint[nod].ym = max(aint[2 * nod].ym, aint[2 * nod + 1].ym);
}
}
static void update(int nod, int st, int dr, int p){
if(st == dr){
aint[nod] = {x[st], x[st], y[st]};
}
else{
int mid = (st + dr) / 2;
if(p <= mid){
update(2 * nod, st, mid, p);
}
else{
update(2 * nod + 1, mid + 1, dr, p);
}
aint[nod].prod = aint[2 * nod].prod * 1LL * aint[2 * nod + 1].prod % mod;
aint[nod].xm = max(aint[2 * nod].xm, aint[2 * nod + 1].xm);
aint[nod].ym = max(aint[2 * nod].ym, aint[2 * nod + 1].ym);
}
}
static void query(int nod, int st, int dr, int p, int u){
if(p <= st && dr <= u){
aux.prod = aux.prod * 1LL * aint[nod].prod % mod;
aux.xm = max(aux.xm, aint[nod].xm);
aux.ym = max(aux.ym, aint[nod].ym);
}
else{
int mid = (st + dr) / 2;
if(p <= mid){
query(2 * nod, st, mid, p, u);
}
if(u > mid){
query(2 * nod + 1, mid + 1, dr, p, u);
}
}
}
static int solve(){
int i, p, u, mid, ind, ymax;
long long val, sol;
val = 1;
for(i = n; i >= 1; i--){
val *= x[i];
if(val > 1000000000){
break;
}
if(x[i] == 1){
p = 1;
u = i;
while(p <= u){
mid = (p + u) / 2;
aux = {1, 0, 0};
query(1, 1, n, mid, i);
if(aux.xm == 1){
u = mid - 1;
}
else{
p = mid + 1;
}
}
lst[p] = i;
i = p;
}
}
val = 1;
sol = 0;
for(i = i + 1; i <= n; i++){
val *= x[i];
if(x[i] != 1){
if(val * y[i] > sol){
sol = val * y[i];
ind = i;
ymax = y[i];
}
}
else{
aux = {1, 0, 0};
query(1, 1, n, i, lst[i]);
if(val * aux.ym > sol){
sol = val * aux.ym;
ind = lst[i];
ymax = aux.ym;
}
i = lst[i];
}
}
aux = {1, 0, 0};
query(1, 1, n, 1, ind);
return aux.prod * 1LL * ymax % mod;
}
int init(int N, int X[], int Y[]) {
n = N;
for(int i = 1; i <= n; i++){
x[i] = X[i - 1];
y[i] = Y[i - 1];
}
build(1, 1, n);
return solve();
}
int updateX(int pos, int val) {
pos++;
x[pos] = val;
update(1, 1, n, pos);
return solve();
}
int updateY(int pos, int val) {
pos++;
y[pos] = val;
update(1, 1, n, pos);
return solve();
}
