# include "horses.h"
# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long
#define pii pair <ll, ll>
const ll NN = 5e5 + 5, inf = 2e9, mod = 1e9 + 7;
long long n, x[NN],y[NN],tree_ml[4 * NN];
pii tree_mx[4 * NN];
long long merge_ml(ll a, ll b) {
return (a * b) % mod;
}
pii merge_mx(pii a, pii b) {
return max(a, b);
}
void build(ll node, ll le, ll ri) {
if (le == ri) {
tree_ml[node] = x[le];
tree_mx[node] = {y[le], le};
return ;
}
ll mid = (le + ri) / 2;
build(2 * node, le, mid);
build(2 * node + 1, mid + 1, ri);
tree_ml[node] = merge_ml(tree_ml[2 * node], tree_ml[2 * node + 1]);
tree_mx[node] = merge_mx(tree_mx[2 * node], tree_mx[2 * node + 1]);
}
void update(ll node, ll le, ll ri, ll idx, ll val, ll ty) {
if (le > idx || ri < idx) return ;
if (le == ri) {
if (ty == 0) tree_ml[node] = x[le];
else tree_mx[node] = {y[le], le};
return ;
}
ll mid = (le + ri) / 2;
update(2 * node,le, mid,idx,val,ty);
update(2 * node + 1, mid + 1, ri, idx,val,ty);
tree_ml[node] = merge_ml(tree_ml[2 * node], tree_ml[2 * node + 1]);
tree_mx[node] = merge_mx(tree_mx[2 * node], tree_mx[2 * node + 1]);
}
ll get_ml(ll node, ll le, ll ri, ll start, ll end) {
if (le > end || ri < start || start > end) return 1LL;
if (le >= start && ri <= end) return tree_ml[node];
ll mid = (le + ri) / 2;
return merge_ml(get_ml(2 * node, le, mid, start,end), get_ml(2 * node + 1, mid + 1, ri, start, end));
}
pii get_mx(ll node, ll le, ll ri, ll start, ll end) {
if (le > end || ri < start || start > end) return {-1e9, 0LL};
if (le >= start && ri <= end) return tree_mx[node];
ll mid = (le + ri) / 2;
return merge_mx(get_mx(2 * node, le, mid,start,end), get_mx(2 * node + 1, mid + 1, ri, start, end));
}
set <ll> s;
ll go() {
auto it = --s.end(); // n + 1
auto it1 = it; it--;
ll cur_mx = 1, cnt = 0, optid = n;
while (true) {
cnt++;
ll st_y = (*it); ll nd_y = (*it1) - 1;
if (st_y == 0) st_y++;
ll mx_y = get_mx(1,1,n,st_y, nd_y).f;
if (mx_y > cur_mx) {
optid = get_mx(1,1,n, st_y, nd_y).s;
cur_mx = mx_y;
}
cur_mx *= x[st_y];
if (it1 == s.begin() || cnt > 32 || cur_mx > inf) break;
it--; it1--;
}
return (get_ml(1,1,n,1,optid) * y[optid]) % mod;
}
int init(int N, int X[], int Y[]) {
n = N;
x[0] = 1; y[0] = 1;
for (int i = 1; i <= n; i++) {
x[i] = X[i - 1]; y[i] = Y[i - 1];
if (x[i] != 1) s.insert(i);
}
s.insert(0); s.insert(n + 1);
build(1, 1, n);
return go();
}
int updateX(int pos, int val) {
pos++;
if (x[pos] != 1) {
s.erase(pos);
}
x[pos] = val;
update(1,1,n, pos,val,0);
if (x[pos] != 1) s.insert(pos);
return go();
}
int updateY(int pos, int val) {
pos++;
y[pos] = val;
update(1,1,n, pos,val, 1);
return go();
}
/*
main() {
int N;
cin>>N;
int *X = (int*)malloc(sizeof(int)*(unsigned int)N);
int *Y = (int*)malloc(sizeof(int)*(unsigned int)N);
for (int i = 0; i < N; i++) {
cin>>X[i];
}
for (int i = 0; i < N; i++) {
cin>>Y[i];
}
cout<<init(N,X,Y)<<"\n";
int M;
cin>>M;
for (int i = 0; i < M; i++) {
int type; cin>>type;
int pos; cin>>pos;
int val; cin>>val;
if (type == 1) {
cout<<updateX(pos,val)<<"\n";
} else if (type == 2) {
cout<<updateY(pos,val)<<"\n";
}
}
return 0;
}*/
