#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
#define ll long long
const ll mod = 1000000007;
const ll mx = 1000000018;
ll n;
ll x[501010], y[501010];
ll t[2010101];
ll Mxt[2010101];
int Ri[2010101];
int Le[2010101];
int prRi[2010101];
int goLe[2010101];
void push(int v, int vl, int vr) {
if (goLe[v] != -2) {
if (vl == vr) {
Le[v] = goLe[v];
} else {
goLe[2 * v] = goLe[v];
goLe[2 * v + 1] = goLe[v];
}
}
if (prRi[v] != -2) {
if (vl == vr) {
Ri[v] = prRi[v];
} else {
prRi[2 * v] = prRi[v];
prRi[2 * v + 1] = prRi[v];
}
}
goLe[v] = -2;
prRi[v] = -2;
}
void updspec(int v, int vl, int vr, int l, int r, int val, int ty) {
push(v, vl, vr);
if (l <= vl && vr <= r) {
if (ty == 1)goLe[v] = val;
if (ty == 2)prRi[v] = val;
push(v, vl, vr);
return;
}
if (r < vl || vr < l)return;
int vm = (vl + vr) / 2;
updspec(2 * v, vl, vm, l, r, val, ty);
updspec(2 * v + 1, vm + 1, vr, l, r, val, ty);
}
pair<int, int> gtspec(int v, int vl, int vr, int pos) {
push(v, vl, vr);
if (vl == vr)return {Le[v], Ri[v]};
int vm = (vl + vr) / 2;
if (pos <= vm)return gtspec(2 * v, vl, vm, pos);
else return gtspec(2 * v + 1, vm + 1, vr, pos);
}
void build(int v, int vl, int vr) {
goLe[v] = -2;
prRi[v] = -2;
if (vl == vr) {
t[v] = x[vl] % mod;
Mxt[v] = vl;
return;
}
int vm = (vl + vr) / 2;
build(2 * v, vl, vm);
build(2 * v + 1, vm + 1, vr);
t[v] = (t[2 * v] * t[2 * v + 1]) % mod;
if (y[Mxt[2 * v]] > y[Mxt[2 * v + 1]])
Mxt[v] = Mxt[2 * v];
else
Mxt[v] = Mxt[2 * v + 1];
}
void upd(int v, int vl, int vr, int pos, ll val) {
if (vl == vr) {
t[v] = val % mod;
return;
}
int vm = (vl + vr) / 2;
if (pos <= vm)upd(2 * v, vl, vm, pos, val);
else upd(2 * v + 1, vm + 1, vr, pos, val);
t[v] = (t[2 * v] * t[2 * v + 1]) % mod;
}
void Mxupd(int v, int vl, int vr, int pos) {
if (vl == vr) {
Mxt[v] = vl;
return;
}
int vm = (vl + vr) / 2;
if (pos <= vm)Mxupd(2 * v, vl, vm, pos);
else Mxupd(2 * v + 1, vm + 1, vr, pos);
if (y[Mxt[2 * v]] > y[Mxt[2 * v + 1]])
Mxt[v] = Mxt[2 * v];
else
Mxt[v] = Mxt[2 * v + 1];
}
ll gt(int v, int vl, int vr, int l, int r) {
if (l <= vl && vr <= r)return t[v] % mod;
if (r < vl || vr < l)return 1ll;
int vm = (vl + vr) / 2;
return (gt(2 * v, vl, vm, l, r) * gt(2 * v + 1, vm + 1, vr, l, r)) % mod;
}
ll Mxgt(int v, int vl, int vr, int l, int r) {
if (l <= vl && vr <= r)return Mxt[v];
if (r < vl || vr < l)return -1;
int vm = (vl + vr) / 2;
ll f = Mxgt(2 * v, vl, vm, l, r);
ll s = Mxgt(2 * v + 1, vm + 1, vr, l, r);
if (f == -1)return s;
if (s == -1)return f;
if (y[f] < y[s])return s;
return f;
}
int opp() {
ll cnt = y[n - 1];
ll last = n - 1;
for (int i = n - 1; i > 0;) {
if (x[i] > mx / cnt)cnt = mx;
else cnt *= x[i];
if (cnt == mx)break;
if (x[i] > 1) {
if (cnt < y[i - 1]){last = i - 1;cnt = y[i - 1];i--;continue;}
}
auto [r, S] = gtspec(1, 0, n - 1, i);
int p = Mxgt(1, 0, n - 1, r, i);
i = r;
if (cnt < y[p]){last = p;cnt = y[p];}
}
ll d = gt(1, 0, n - 1, 0, last);
return ((d % mod) * (y[last] % mod)) % mod;
}
int init(int N, int X[], int Y[]) {
n = N;
for (ll i = 0; i < n; i++) {
x[i] = X[i];
y[i] = Y[i];
}
build(1, 0, n - 1);
int lft = -1;
for (int i = 0; i < n; i++) {
updspec(1, 0, n - 1, i, i, lft, 1);
if (x[i] > 1)lft = i;
}
int rgt = n;
for (int i = n - 1; i >= 0; i--) {
updspec(1, 0, n - 1, i, i, rgt, 2);
if (x[i] > 1)rgt = i;
}
// for (int i = 0; i < n; i++) {
// auto qq = gtspec(1, 0, n - 1, i);
// s << i << " -- " << qq.first << " " << qq.second << endl;
// }
return opp();
}
int updateX(int pos, int val) {
x[pos] = val;
upd(1, 0, n - 1, pos, val);
if (val == 0)exit(1);
if (val == 1) {
auto [Lf, Rt] = gtspec(1, 0, n - 1, pos);
updspec(1, 0, n - 1, Lf + 1, Rt, Lf, 1);
updspec(1, 0, n - 1, Lf, Rt - 1, Rt, 2);
} else {
auto [Lf, Rt] = gtspec(1, 0, n - 1, pos);
updspec(1, 0, n - 1, pos + 1, Rt, pos, 1);
updspec(1, 0, n - 1, Lf, pos - 1, pos, 2);
}
return opp();
}
int updateY(int pos, int val) {
y[pos] = val;
Mxupd(1, 0, n - 1, pos);
return opp();
}
