#include <bits/stdc++.h>
using namespace std;
// Constants and Globals
const int MOD = 1e9 + 7;
const int MAXN = 500005;
int n;
int x[MAXN], y[MAXN];
set<int> s; // Stores indices where x[i] > 1
// Segment Tree for Product of X (Modulo 1e9+7)
struct TreeX {
int t[4 * MAXN];
void build(int i, int l, int r) {
if (l == r) {
t[i] = x[l] % MOD;
return;
}
int m = (l + r) >> 1;
build(2 * i, l, m);
build(2 * i + 1, m + 1, r);
t[i] = (1LL * t[2 * i] * t[2 * i + 1]) % MOD;
}
void update(int i, int l, int r, int p, int v) {
if (l == r) {
t[i] = v % MOD;
return;
}
int m = (l + r) >> 1;
if (p <= m) update(2 * i, l, m, p, v);
else update(2 * i + 1, m + 1, r, p, v);
t[i] = (1LL * t[2 * i] * t[2 * i + 1]) % MOD;
}
int query(int i, int l, int r, int ql, int qr) {
if (ql > r || qr < l) return 1;
if (ql <= l && r <= qr) return t[i];
int m = (l + r) >> 1;
return (1LL * query(2 * i, l, m, ql, qr) * query(2 * i + 1, m + 1, r, ql, qr)) % MOD;
}
} st_x;
// Segment Tree for Maximum Y
struct TreeY {
int t[4 * MAXN];
void build(int i, int l, int r) {
if (l == r) {
t[i] = y[l];
return;
}
int m = (l + r) >> 1;
build(2 * i, l, m);
build(2 * i + 1, m + 1, r);
t[i] = max(t[2 * i], t[2 * i + 1]);
}
void update(int i, int l, int r, int p, int v) {
if (l == r) {
t[i] = v;
return;
}
int m = (l + r) >> 1;
if (p <= m) update(2 * i, l, m, p, v);
else update(2 * i + 1, m + 1, r, p, v);
t[i] = max(t[2 * i], t[2 * i + 1]);
}
int query(int i, int l, int r, int ql, int qr) {
if (ql > r || qr < l) return 0;
if (ql <= l && r <= qr) return t[i];
int m = (l + r) >> 1;
return max(query(2 * i, l, m, ql, qr), query(2 * i + 1, m + 1, r, ql, qr));
}
} st_y;
// Core logic to find the maximum profit
int solve() {
vector<int> idx;
auto it = s.rbegin();
// 1. Gather relevant indices from right to left
// We only need enough X's such that their product exceeds 1e9,
// because Max(Y) is 1e9. Older X's would just make the prefix multiplier huge.
long long cur_check = 1;
while (it != s.rend()) {
idx.push_back(*it);
cur_check *= x[*it];
// 1e9 + 7 is a safe upper bound check to cover Max Y range
if (cur_check > 1000000007) break;
it++;
}
// Always consider the start of the array to cover the range [0, first_non_one)
if (idx.empty() || idx.back() != 0) idx.push_back(0);
reverse(idx.begin(), idx.end());
long long best_val = -1;
long long cur_prod = 1; // Stores accumulated X within the window
// 2. Iterate through the window of indices
for (size_t i = 0; i < idx.size(); i++) {
int p = idx[i];
// The current block ends before the next interesting index, or at the end of array
int r = (i + 1 < idx.size()) ? idx[i+1] - 1 : n - 1;
// Multiply by X at the current start position
cur_prod *= x[p];
// Find max Y in this block [p, r]
// Note: X values from p+1 to r are all 1, so cur_prod is valid for the whole range
int max_y_in_range = st_y.query(1, 0, n - 1, p, r);
// Compare relative profit
if (cur_prod * max_y_in_range > best_val) {
best_val = cur_prod * max_y_in_range;
}
}
// 3. Calculate final result modulo 1e9+7
// Result = (PrefixProduct_Before_Window * Best_Relative_Value) % MOD
long long prefix_prod = st_x.query(1, 0, n - 1, 0, idx[0] - 1);
long long ans = (prefix_prod * (best_val % MOD)) % MOD;
return (int)ans;
}
int init(int N, int X[], int Y[]) {
n = N;
for (int i = 0; i < n; i++) {
x[i] = X[i];
y[i] = Y[i];
if (x[i] > 1) s.insert(i);
}
st_x.build(1, 0, n - 1);
st_y.build(1, 0, n - 1);
return solve();
}
int updateX(int pos, int val) {
if (x[pos] > 1) s.erase(pos);
x[pos] = val;
if (x[pos] > 1) s.insert(pos);
st_x.update(1, 0, n - 1, pos, val);
return solve();
}
int updateY(int pos, int val) {
y[pos] = val;
st_y.update(1, 0, n - 1, pos, val);
return solve();
}
