#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int MAXN = 500005;
int n;
int curX[MAXN], curY[MAXN];
ll treeX[4 * MAXN];
int treeY[4 * MAXN];
set<int> st;
// Segment Tree for Product of X (modulo 10^9 + 7)
void buildX(int node, int start, int end) {
if (start == end) {
treeX[node] = curX[start];
return;
}
int mid = (start + end) / 2;
buildX(2 * node, start, mid);
buildX(2 * node + 1, mid + 1, end);
treeX[node] = (treeX[2 * node] * treeX[2 * node + 1]) % MOD;
}
void updX(int node, int start, int end, int idx, int val) {
if (start == end) {
treeX[node] = val;
return;
}
int mid = (start + end) / 2;
if (idx <= mid) updX(2 * node, start, mid, idx, val);
else updX(2 * node + 1, mid + 1, end, idx, val);
treeX[node] = (treeX[2 * node] * treeX[2 * node + 1]) % MOD;
}
ll queryX(int node, int start, int end, int l, int r) {
if (r < start || end < l) return 1;
if (l <= start && end <= r) return treeX[node];
int mid = (start + end) / 2;
return (queryX(2 * node, start, mid, l, r) * queryX(2 * node + 1, mid + 1, end, l, r)) % MOD;
}
// Segment Tree for Maximum of Y
void buildY(int node, int start, int end) {
if (start == end) {
treeY[node] = curY[start];
return;
}
int mid = (start + end) / 2;
buildY(2 * node, start, mid);
buildY(2 * node + 1, mid + 1, end);
treeY[node] = max(treeY[2 * node], treeY[2 * node + 1]);
}
void updY(int node, int start, int end, int idx, int val) {
if (start == end) {
treeY[node] = val;
return;
}
int mid = (start + end) / 2;
if (idx <= mid) updY(2 * node, start, mid, idx, val);
else updY(2 * node + 1, mid + 1, end, idx, val);
treeY[node] = max(treeY[2 * node], treeY[2 * node + 1]);
}
int queryY(int node, int start, int end, int l, int r) {
if (r < start || end < l) return 0;
if (l <= start && end <= r) return treeY[node];
int mid = (start + end) / 2;
return max(queryY(2 * node, start, mid, l, r), queryY(2 * node + 1, mid + 1, end, l, r));
}
int solve() {
// Collect last ~30 positions where X[i] > 1
vector<int> pos;
auto it = st.end();
ll prod = 1;
for (int i = 0; i < 35 && it != st.begin(); i++) {
it--;
pos.push_back(*it);
prod *= curX[*it];
if (prod > 2e9) break; // Optimization: past 10^9, previous years can't win
}
reverse(pos.begin(), pos.end());
// Candidates for best selling year
int best_pos_idx = -1; // -1 represents the interval before the first X > 1
int cur_best_y = (pos.empty() ? queryY(1, 0, n - 1, 0, n - 1) : queryY(1, 0, n - 1, 0, pos[0] - 1));
for (int i = 0; i < (int)pos.size(); i++) {
int L = pos[i];
int R = (i + 1 < (int)pos.size()) ? pos[i + 1] - 1 : n - 1;
int m_i = queryY(1, 0, n - 1, L, R);
ll p = 1;
int start_search = (best_pos_idx == -1) ? 0 : best_pos_idx + 1;
for (int k = start_search; k <= i; k++) {
p *= curX[pos[k]];
if (p > 2e9) break;
}
if (p >= 2e9 || p * m_i >= cur_best_y) {
cur_best_y = m_i;
best_pos_idx = i;
}
}
ll ans_prod = 1;
if (best_pos_idx != -1) ans_prod = queryX(1, 0, n - 1, 0, pos[best_pos_idx]);
return (ans_prod * cur_best_y) % MOD;
}
int init(int N, int X[], int Y[]) {
n = N;
for (int i = 0; i < n; i++) {
curX[i] = X[i];
curY[i] = Y[i];
if (X[i] > 1) st.insert(i);
}
buildX(1, 0, n - 1);
buildY(1, 0, n - 1);
return solve();
}
int updateX(int pos, int val) {
if (curX[pos] > 1) st.erase(pos);
curX[pos] = val;
if (curX[pos] > 1) st.insert(pos);
updX(1, 0, n - 1, pos, val);
return solve();
}
int updateY(int pos, int val) {
curY[pos] = val;
updY(1, 0, n - 1, pos, val);
return solve();
}
