// clang-format off
#include <bits/stdc++.h>
using i64 = int64_t;
template <typename T> bool setmax(T &v, const T a) {
if (v < a) {
v = a;
return true;
} else {
return false;
}
}
int N;
std::vector<int> X, Y;
constexpr i64 mod = 1000000007;
constexpr int max_v = 1000000000;
i64 mul(i64 v, i64 d) {
return v * d % mod;
}
template <class M>
class SegmentTree {
using T = typename M::Type;
int n, size;
std::vector<T> data;
void update(const int i) {
assert(0 <= i and i < size);
data[i] = M::op(data[2 * i], data[2 * i + 1]);
}
public:
SegmentTree() = default;
SegmentTree(int n_) : n(n_) {
size = 1;
while (size < n) size <<= 1;
data.assign(2 * size, M::id());
}
void set(int i, const T v) {
assert(0 <= i and i < n);
i += size;
data[i] = v;
while (i != 1) {
i >>= 1;
update(i);
}
}
T fold(int l, int r) {
assert(0 <= l and l <= r and r <= n);
T vl = M::id(), vr = M::id();
for (l += size, r += size; l < r; l >>= 1, r >>= 1) {
if (l & 1) vl = M::op(vl, data[l++]);
if (r & 1) vr = M::op(data[--r], vr);
}
return M::op(vl, vr);
}
template <class F> int min_left(int r, const F& f) {
assert(0 <= r and r <= n);
assert(f(M::id()));
if (r == 0) return 0;
r += size;
T p = M::id();
do {
--r;
while (r > 1 and (r & 1)) r >>= 1;
if (not f(M::op(data[r], p))) {
while (r < size) {
r = 2 * r + 1;
if (f(M::op(data[r], p))) p = M::op(data[r--], p);
}
return r + 1 - size;
}
p = M::op(data[r], p);
} while ((r & -r) != r);
return 0;
}
};
struct Monoid_Mul {
using Type = i64;
static Type op(Type a, Type b) { return mul(a, b); }
static Type id() { return 1; }
};
struct Monoid_Max {
using Type = std::pair<i64, int>;
static Type op(Type a, Type b) { return std::max(a, b); }
static Type id() { return {0, 0}; }
};
SegmentTree<Monoid_Mul> mulseg;
SegmentTree<Monoid_Max> xseg, yseg;
int calc() {
i64 v = 1;
double best = (double)Y[N - 1];
int best_pos = N - 1, r = N;
while (v <= max_v and r != 0) {
int nxt = xseg.min_left(r, [](const std::pair<i64, int> p) { return p.first <= 1; });
if (nxt == 0) {
if (setmax(best, (double)yseg.fold(nxt, r).first / (double)v)) {
best_pos = yseg.fold(nxt, r).second;
}
break;
} else {
--nxt;
if (setmax(best, (double)yseg.fold(nxt, r).first / (double)v)) {
best_pos = yseg.fold(nxt, r).second;
}
v *= X[nxt];
r = nxt;
}
}
/*
for (int i = N - 2; i >= 0; --i) {
v *= X[i + 1];
if (setmax(best, (double)Y[i] / (double)v)) {
best_pos = i;
}
if (v > max_v) break;
}
*/
return (int)mul(mulseg.fold(0, best_pos + 1), Y[best_pos]);
}
int minit(int n, std::vector<int> x, std::vector<int> y) {
N = n;
X = std::move(x);
Y = std::move(y);
mulseg = SegmentTree<Monoid_Mul>(N);
xseg = yseg = SegmentTree<Monoid_Max>(N);
for (int i = 0; i < N; ++i) {
mulseg.set(i, X[i]);
xseg.set(i, {X[i], i});
yseg.set(i, {Y[i], i});
}
return calc();
}
int mupdateX(int pos, int val) {
X[pos] = val;
mulseg.set(pos, val);
xseg.set(pos, {X[pos], pos});
return calc();
}
int mupdateY(int pos, int val) {
Y[pos] = val;
yseg.set(pos, {Y[pos], pos});
return calc();
}
int init(int N, int X[], int Y[]) {
std::vector<int> x(N), y(N);
for (int i = 0; i < N; ++i) {
x[i] = X[i];
y[i] = Y[i];
}
return minit(N, x, y);
}
int updateX(int pos, int val) {
return mupdateX(pos, val);
}
int updateY(int pos, int val) {
return mupdateY(pos, val);
}
