#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
template <long long mod>
struct modular {
long long value;
modular(long long x = 0) {
value = x % mod;
if (value < 0) value += mod;
}
modular& operator+=(const modular& other) {
if ((value += other.value) >= mod) value -= mod;
return *this;
}
modular& operator-=(const modular& other) {
if ((value -= other.value) < 0) value += mod;
return *this;
}
modular& operator*=(const modular& other) {
value = value * other.value % mod;
return *this;
}
modular& operator/=(const modular& other) {
long long a = 0, b = 1, c = other.value, m = mod;
while (c != 0) {
long long t = m / c;
m -= t * c;
swap(c, m);
a -= t * b;
swap(a, b);
}
a %= mod;
if (a < 0) a += mod;
value = value * a % mod;
return *this;
}
friend modular operator+(const modular& lhs, const modular& rhs) { return modular(lhs) += rhs; }
friend modular operator-(const modular& lhs, const modular& rhs) { return modular(lhs) -= rhs; }
friend modular operator*(const modular& lhs, const modular& rhs) { return modular(lhs) *= rhs; }
friend modular operator/(const modular& lhs, const modular& rhs) { return modular(lhs) /= rhs; }
modular& operator++() { return *this += 1; }
modular& operator--() { return *this -= 1; }
modular operator++(int) {
modular res(*this);
*this += 1;
return res;
}
modular operator--(int) {
modular res(*this);
*this -= 1;
return res;
}
modular operator-() const { return modular(-value); }
bool operator==(const modular& rhs) const { return value == rhs.value; }
bool operator!=(const modular& rhs) const { return value != rhs.value; }
bool operator<(const modular& rhs) const { return value < rhs.value; }
};
template <long long mod>
string to_string(const modular<mod>& x) {
return to_string(x.value);
}
template <long long mod>
ostream& operator<<(ostream& stream, const modular<mod>& x) {
return stream << x.value;
}
template <long long mod>
istream& operator>>(istream& stream, modular<mod>& x) {
stream >> x.value;
x.value %= mod;
if (x.value < 0) x.value += mod;
return stream;
}
constexpr long long mod = (long long) 1e9 + 7;
using mint = modular<mod>;
mint power(mint a, long long n) {
mint res = 1;
while (n > 0) {
if (n & 1) {
res *= a;
}
a *= a;
n >>= 1;
}
return res;
}
vector<mint> fact(1, 1);
vector<mint> finv(1, 1);
mint C(int n, int k) {
if (n < k || k < 0) {
return mint(0);
}
while ((int) fact.size() < n + 1) {
fact.emplace_back(fact.back() * (int) fact.size());
finv.emplace_back(mint(1) / fact.back());
}
return fact[n] * finv[k] * finv[n - k];
}
struct segtree {
struct T {
int mx;
mint prod;
};
int n;
int size;
vector<T> node;
T e() {
return T{-1, mint(1)};
}
T op(T x, T y) {
return T{max(x.mx, y.mx), x.prod * y.prod};
}
segtree() : segtree(0) {}
segtree(int _n) {
build(vector<T>(_n, e()));
}
segtree(const vector<T>& v) {
build(v);
}
void build(const vector<T>& v) {
n = (int) v.size();
if (n <= 1) {
size = n;
} else {
size = 1 << (32 - __builtin_clz(n - 1));
}
node.resize(2 * size, e());
for (int i = 0; i < n; i++) {
node[i + size] = v[i];
}
for (int i = size - 1; i > 0; i--) {
node[i] = op(node[2 * i], node[2 * i + 1]);
}
}
void set(int p, T v) {
assert(0 <= p && p < n);
p += size;
node[p] = v; // update
// node[p] += v; // add
while (p > 1) {
p >>= 1;
node[p] = op(node[2 * p], node[2 * p + 1]);
}
}
T get(int l, int r) {
assert(0 <= l && l <= r && r <= n);
T vl = e();
T vr = e();
l += size;
r += size;
while (l < r) {
if (l & 1) {
vl = op(vl, node[l++]);
}
if (r & 1) {
vr = op(node[--r], vr);
}
l >>= 1;
r >>= 1;
}
return op(vl, vr);
}
T get(int p) {
assert(0 <= p && p < n);
return node[p + size];
}
};
int n;
int* x;
int* y;
set<int> st;
segtree seg;
int f() {
long long prod = 1;
vector<int> c;
auto iter = st.rbegin();
while (prod < (int) 1e9 && iter != st.rend()) {
c.emplace_back(*iter);
prod *= x[*iter];
iter++;
}
long long t = 1;
for (int i : c) {
t = max(t, prod * seg.get(i, n).mx);
prod /= x[i];
}
mint ans = t;
ans *= seg.get(0, c.back()).prod;
return (int) ans.value;
}
int init(int _n, int _x[], int _y[]) {
n = _n;
x = _x;
y = _y;
st.emplace(0);
for (int i = 0; i < n; i++) {
if (x[i] > 1) {
st.emplace(i);
}
}
seg = segtree(n);
for (int i = 0; i < n; i++) {
seg.set(i, segtree::T{y[i], x[i]});
}
return f();
}
int updateX(int pos, int val) {
x[pos] = val;
if (x[pos] > 1) {
st.emplace(pos);
} else if (pos != 0) {
st.erase(pos);
}
seg.set(pos, segtree::T{y[pos], x[pos]});
return f();
}
int updateY(int pos, int val) {
y[pos] = val;
seg.set(pos, segtree::T{y[pos], x[pos]});
return f();
}
#ifdef tabr
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int _n = 3;
int _x[] = {2, 1, 3};
int _y[] = {3, 4, 1};
cout << init(_n, _x, _y) << '\n';
cout << updateY(1, 2) << '\n';
return 0;
}
#endif
