// 0 indexed btw
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define lint long long
#define arr array
#define pli pair<lint, int>
#define pii pair<int, int>
#define fir first
#define sec second
#define vec vector
const int N = 5e5 + 5, INF = 2e9;
const lint MD = 1e9 + 7;
int n;
arr<lint, N> grw, prc;
lint md(lint x) { return (x + MD) % MD; }
struct Prd_Sg {
arr<lint, 5 * N> sg;
void bld(int u = 1, int lw = 1, int hg = n) {
if (lw == hg) { sg[u] = grw[lw]; return; }
int mdl = (lw + hg) / 2;
bld(2 * u, lw, mdl), bld(2 * u + 1, mdl + 1, hg);
sg[u] = md(sg[2 * u] * sg[2 * u + 1]);
}
void upd(int i, lint x, int u = 1, int lw = 1, int hg = n) {
if (i < lw || hg < i) return;
if (lw == hg) { sg[u] = x; return; }
int mdl = (lw + hg) / 2;
upd(i, x, 2 * u, lw, mdl), upd(i, x, 2 * u + 1, mdl + 1, hg);
sg[u] = md(sg[2 * u] * sg[2 * u + 1]);
}
lint qry(int l, int r, int u = 1, int lw = 1, int hg = n) {
if (r < lw || hg < l) return 1;
if (l <= lw && hg <= r) return sg[u];
int mdl = (lw + hg) / 2;
return md(qry(l, r, 2 * u, lw, mdl) * qry(l, r, 2 * u + 1, mdl + 1, hg));
}
} prd_sg;
set<pair<pii, lint>> rng;
struct Mx_Sg {
arr<pli, 5 * N> sg;
void bld(int u = 1, int lw = 1, int hg = n) {
if (lw == hg) { sg[u] = {prc[lw], lw}; return; }
int md = (lw + hg) / 2;
bld(2 * u, lw, md), bld(2 * u + 1, md + 1, hg);
sg[u] = max(sg[2 * u], sg[2 * u + 1]);
}
void upd(int i, int x, int u = 1, int lw = 1, int hg = n) {
if (i < lw || hg < i) return;
if (lw == hg) { sg[u] = {x, lw}; return; }
int md = (lw + hg) / 2;
upd(i, x, 2 * u, lw, md), upd(i, x, 2 * u + 1, md + 1, hg);
sg[u] = max(sg[2 * u], sg[2 * u + 1]);
}
pli qry(int l, int r, int u = 1, int lw = 1, int hg = n) {
if (r < lw || hg < l) return {-1, -1};
if (l <= lw && hg <= r) return sg[u];
int md = (lw + hg) / 2;
return max(qry(l, r, 2 * u, lw, md), qry(l, r, 2 * u + 1, md + 1, hg));
}
} mx_sg;
vec<pair<pii, lint>> sf;
lint slv() {
int cnt = 0;
for (auto it = rng.rbegin(); it != rng.rend() && cnt <= 64; it++, cnt++) sf.push_back(*it);
reverse(sf.begin(), sf.end());
int bst = 0;
lint grw_prd = 1;
for (pair<pii, lint> x : sf) {
grw_prd *= x.sec;
if (grw_prd > prc[bst] || grw_prd * mx_sg.qry(x.fir.fir, x.fir.sec).fir > prc[bst]) {
bst = mx_sg.qry(x.fir.fir, x.fir.sec).sec;
grw_prd = 1;
}
}
assert(bst != 0);
lint ans = md(prd_sg.qry(1, bst) * prc[bst]);
return ans;
}
int init(int _n, int _grw[], int _prc[]) {
n = _n;
for (int i = 1; i <= n; i++) grw[i] = _grw[i - 1], prc[i] = _prc[i - 1];
prd_sg.bld(), mx_sg.bld();
for (int i = 1; i <= n; i++) {
if (rng.size() && rng.rbegin()->sec == 1 && grw[i] == 1) {
pii x = rng.rbegin()->fir;
rng.erase(--rng.end());
rng.insert({{x.fir, i}, 1});
} else rng.insert({{i, i}, grw[i]});
}
// for (pair<pii, lint> x : rng) cout << x.fir.fir << " " << x.fir.sec << ": " << x.sec << endl;
return slv();
}
int updateX(int id, int vl) {
id++;
if (grw[id] != 1 && vl != 1) {
rng.erase({{id, id}, grw[id]});
rng.insert({{id, id}, vl});
} else if (grw[id] != 1 && vl == 1) {
rng.erase({{id, id}, grw[id]});
rng.insert({{id, id}, vl});
auto it = rng.find({{id, id}, vl});
if (it != rng.begin() && next(it, -1)->sec == 1) {
pair<pii, lint> x = *it, y = *next(it, -1);
rng.erase(x), rng.erase(y);
it = rng.insert({{y.fir.fir, id}, 1}).fir;
}
if (next(it, 1) != rng.end() && next(it, 1)->sec == 1) {
pair<pii, lint> x = *it, y = *next(it, 1);
rng.erase(x), rng.erase(y);
it = rng.insert({{id, y.fir.sec}, 1}).fir;
}
} else if (grw[id] == 1 && vl != 1) {
auto it = --rng.upper_bound({{id, INF}, INF});
if (it->fir.fir != id) {
pair<pii, lint> x = *it;
rng.erase(it);
rng.insert({{x.fir.fir, id - 1}, 1});
it = rng.insert({{id, x.fir.sec}, 1}).fir;
}
if (it->fir.sec != id) {
pair<pii, lint> x = *it;
rng.erase(it);
rng.insert({{id + 1, x.fir.sec}, 1});
it = rng.insert({{id, id}, 1}).fir;
}
rng.erase({{id, id}, grw[id]});
rng.insert({{id, id}, vl});
} else;
// for (pair<pii, lint> x : rng) cout << x.fir.fir << " " << x.fir.sec << ": " << x.sec << endl;
grw[id] = vl;
prd_sg.upd(id, vl);
return slv();
}
int updateY(int id, int vl) {
id++, prc[id] = vl;
mx_sg.upd(id, vl);
return slv();
}
