#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
using i64 = long long;
constexpr int mod = 1e9 + 7;
struct SegmentTree {
int n;
vector<i64> t;
void init(int _n) {
n = _n;
t.assign(4 * n, 1);
}
void update(int id, int tl, int tr, int i, i64 v) {
if (tl == tr) {
t[id] = v;
return;
}
int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
if (i <= tm) {
update(x, tl, tm, i, v);
} else {
update(y, tm + 1, tr, i, v);
}
t[id] = t[x] * t[y] % mod;
}
i64 get(int id, int tl, int tr, int l, int r) {
if (r < tl || tr < l) return 1;
if (l <= tl && tr <= r) return t[id];
int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
return get(x, tl, tm, l, r) * get(y, tm + 1, tr, l, r) % mod;
}
void update(int i, int v) { update(0, 0, n - 1, i, v); }
i64 get(int l, int r) { return get(0, 0, n - 1, l, r); }
};
struct mxSegmentTree {
int n;
vector<int> t;
void init(int _n) {
n = _n;
t.resize(4 * n);
}
int merge(int x, int y) {
return max(x, y);
}
void update(int id, int tl, int tr, int i, int v) {
if (tl == tr) {
t[id] = v;
return;
}
int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
if (i <= tm) {
update(x, tl, tm, i, v);
} else {
update(y, tm + 1, tr, i, v);
}
t[id] = merge(t[x], t[y]);
}
i64 get(int id, int tl, int tr, int l, int r) {
if (r < tl || tr < l) return 0LL;
if (l <= tl && tr <= r) return t[id];
int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
return merge(get(x, tl, tm, l, r), get(y, tm + 1, tr, l, r));
}
void update(int i, int v) { update(0, 0, n - 1, i, v); }
i64 get(int l, int r) { return get(0, 0, n - 1, l, r); }
};
int n;
SegmentTree t;
mxSegmentTree mx;
vector<i64> x, y;
vector<pair<i64, i64>> b;
set<i64> s;
i64 pos, ans;
bool is(int l, int r) {
i64 k = mx.get(r, n - 1);
i64 to = mx.get(l, n - 1);
if (k > y[l]) return true;
auto it = s.upper_bound(l);
while (it != s.end()) {
if (*it > r) break;
k *= x[*it];
if (k > to) return true;
it++;
}
return false;
}
void solve() {
vector<i64> id;
if (s.empty()) {
pos = 0;
ans = mx.get(0, n - 1);
return;
}
auto it = s.end();
while (id.size() < 40 && it != s.begin()) {
--it;
id.push_back(*it);
}
ranges::reverse(id);
pos = id[0];
ans = (t.get(0, pos) * mx.get(pos, n - 1)) % mod;
for (int i = 1; i < id.size(); i++) {
if (is(pos, id[i])) {
pos = id[i];
ans = (t.get(0, pos) * mx.get(pos, n - 1)) % mod;
}
}
}
int init(int N, int X[], int Y[]) {
n = N;
x.assign(X, X + N);
y.assign(Y, Y + N);
t.init(n);
mx.init(n);
for (int i = 0; i < n; i++) {
if (x[i] > 1) {
s.insert(i);
}
t.update(i, x[i]);
mx.update(i, y[i]);
}
solve();
return ans;
}
int updateX(int i, int val) {
if (x[i] > 1) s.erase(i);
if (val > 1) s.insert(i);
t.update(i, val);
x[i] = val;
solve();
return ans;
}
int updateY(int i, int val) {
y[i] = val;
mx.update(i, val);
solve();
return ans;
}
