#include <bits/stdc++.h>
using namespace std;
#include "horses.h"
const long long N = 5e5 + 5, M = 1e9 + 7;
long long n, cur, x[N], y[N];
struct node {
long long mxy = 0, px = 1;
long long left = -1, right = -1;
};
vector<node> T;
set<long long> st;
node join(node a, node b) {
node ans;
ans.px = (a.px * b.px) % M;
ans.mxy = max(a.mxy, b.mxy);
return ans;
}
void build(long long v = 0, long long s = 0, long long e = n) {
if (e - s == 1) {
T[v].mxy = y[s];
T[v].px = x[s] % M;
return;
}
T[v].left = ++cur;
T[v].right = ++cur;
long long lc = T[v].left, rc = T[v].right, mid = (s + e) / 2;
build(lc, s, mid);
build(rc, mid, e);
T[v] = join(T[lc], T[rc]);
}
node query(long long l, long long r, long long v = 0, long long s = 0, long long e = n) {
if (l <= s && e <= r) return T[v];
long long mid = (s + e) / 2, lc = T[v].left, rc = T[v].right;
if (r <= mid) return query(l, r, lc, s, mid);
if (l >= mid) return query(l, r, rc, mid, e);
return join(query(l, r, lc, s, mid), query(l, r, rc, mid, e));
}
void updx(long long pos, long long val, long long v = 0, long long s = 0, long long e = n) {
if (e - s == 1) {
T[v].px = val % M;
return;
}
long long mid = (s + e) / 2, lc = T[v].left, rc = T[v].right;
if (pos < mid) updx(pos, val, lc, s, mid);
else updx(pos, val, rc, mid, e);
T[v] = join(T[lc], T[rc]);
}
void updy(long long pos, long long val, long long v = 0, long long s = 0, long long e = n) {
if (e - s == 1) {
T[v].mxy = val;
return;
}
long long mid = (s + e) / 2, lc = T[v].left, rc = T[v].right;
if (pos < mid) updy(pos, val, lc, s, mid);
else updy(pos, val, rc, mid, e);
T[v] = join(T[lc], T[rc]);
}
int solve() {
vector<long long> cands;
cands.push_back(0);
if (!st.empty()) {
auto it = st.end(); it--;
vector<long long> last_growth;
long long pd = 1;
for (int i = 0; i < 32; i++) {
last_growth.push_back(*it);
pd *= x[*it];
if (it == st.begin() || pd > 2e9) break;
it--;
}
reverse(last_growth.begin(), last_growth.end());
for (long long idx : last_growth) {
if (idx != 0) cands.push_back(idx);
}
}
sort(cands.begin(), cands.end());
cands.erase(unique(cands.begin(), cands.end()), cands.end());
long long best = cands[0];
for (size_t i = 1; i < cands.size(); i++) {
long long curr = cands[i];
long long growth = 1;
for (long long k = best + 1; k <= curr; k++) {
growth *= x[k];
if (growth > 1e9) break;
}
long long nxt = (i + 1 < cands.size() ? cands[i + 1] : n);
long long cy = query(curr, nxt).mxy;
long long by = query(best, curr).mxy;
if (growth > 1e9 || growth * cy >= by) best = curr;
}
long long px = query(0, best + 1).px;
long long ed = n;
auto nit = st.upper_bound(best);
if (nit != st.end()) ed = *nit;
long long my = query(best, ed).mxy;
return (int)((px * my) % M);
}
int init(int N_val, int X[], int Y[]) {
n = N_val; cur = 0; st.clear();
for (int i = 0; i < n; i++) {
x[i] = X[i]; y[i] = Y[i];
if (x[i] > 1) st.insert(i);
}
T.assign(2 * n + 10, node());
build();
return solve();
}
int updateX(int pos, int val) {
if (x[pos] > 1) st.erase(pos);
x[pos] = val;
if (x[pos] > 1) st.insert(pos);
updx(pos, val);
return solve();
}
int updateY(int pos, int val) {
y[pos] = val;
updy(pos, val);
return solve();
}
