#include "horses.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;
const int MAX_N = 5e5 + 5;
const int mod = 1e9 + 7;
const int infinity = 1e9;
struct Seg {
int n;
vi seg;
vb moded;
Seg () {}
Seg (int m) {
for (n = 1; n < m; n <<= 1);
seg.resize(2 * n, 1);
moded.resize(2 * n);
}
void pull(int i) {
seg[i] = seg[i << 1] * seg[i << 1 | 1];
moded[i] = moded[i << 1] | moded[i << 1 | 1];
}
void update(int i, ll x) {
seg[i += n] = x;
for (i >>= 1; i; i >>= 1) {
pull(i);
if (seg[i] >= mod) {
moded[i] = true;
seg[i] %= mod;
}
}
}
pair<ll, bool> query(int l, int r) {
pair<ll, bool> p = {1, false};
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) {
p.x *= seg[l];
p.y |= moded[l];
l++;
}
if (r & 1) {
r--;
p.x *= seg[r];
p.y |= moded[r];
}
if (p.x >= mod) {
p.y = true;
p.x %= mod;
}
}
return p;
}
};
struct SegMax {
int n;
vi seg;
SegMax () {}
SegMax (int m) {
for (n = 1; n < m; n <<= 1);
seg.resize(2 * n);
}
void update(int i, int x) {
seg[i += n] = x;
for (i >>= 1; i; i >>= 1) {
seg[i] = max(seg[i << 1], seg[i << 1 | 1]);
}
}
ll query(int l, int r) {
ll ans = 0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) chkmax(ans, seg[l++]);
if (r & 1) chkmax(ans, seg[--r]);
}
return ans;
}
};
int n;
ll x[MAX_N], y[MAX_N];
set<int, greater<int>> changed;
Seg seg;
SegMax seg_max;
pii Comp(pii p1, pii p2) {
if (p1.x > p2.x) swap(p1, p2);
auto [v, moded] = seg.query(p1.x + 1, p2.x + 1);
if (moded) return p2;
ll y1 = seg_max.query(p1.x, p1.y), y2 = seg_max.query(p2.x, p2.y);
return (y1 < v * y2 ? p2 : p1);
}
int Solve() {
pii best = {0, 1};
int cnt = 30;
int last = n;
for (int i : changed) {
if (!(cnt--)) break;
best = Comp({i, last}, best);
last = i;
}
ll x1 = seg.query(0, best.x + 1).x;
ll y1 = seg_max.query(best.x, best.y);
return x1 * y1 % mod;
}
int init(int N, int X[], int Y[]) {
n = N;
seg = Seg(n);
seg_max = SegMax(n);
for (int i = 0; i < n; i++) {
x[i] = X[i], y[i] = Y[i];
if (x[i] != 1) changed.insert(i);
seg_max.update(i, y[i]);
seg.update(i, x[i]);
}
return Solve();
}
int updateX(int pos, int val) {
if (x[pos] != 1) changed.erase(changed.find(pos));
x[pos] = val;
if (x[pos] != 1) changed.insert(pos);
seg.update(pos, val);
return Solve();
}
int updateY(int pos, int val) {
y[pos] = val;
seg_max.update(pos, val);
return Solve();
}
