#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
using ll = long long;
using i128 = __int128;
constexpr int MOD = 1e9 + 7;
int add(int a, int b) {
return a + b < MOD ? a + b : a + b - MOD;
}
int mul(int a, int b) {
return a * (long long) b % MOD;
}
int sub(int a, int b) {
return a >= b ? a - b : a - b + MOD;
}
int power(int a, int b) {
int ans = 1;
for (; b > 0; b >>= 1, a = mul(a, a)) if (b & 1) ans = mul(ans, a);
return ans;
}
int inv(int a) {
return power(a, MOD - 2);
}
struct segtreeY {
vector<int> t;
int sz = 1;
void init(vector<int> a) {
sz = 1;
while (sz < a.size()) sz <<= 1;
t.assign(sz << 1, 0);
for (int i = 0; i < a.size(); ++i) {
t[i + sz] = a[i];
}
for (int i = sz - 1; i > 0; --i) {
t[i] = max(t[i << 1], t[i << 1 | 1]);
}
}
void pull(int x) {
t[x] = max(t[x << 1], t[x << 1 | 1]);
}
void modify(int i, int val) {
modify(i, val, 1, 0, sz);
}
void modify(int i, int val, int x, int lx, int rx) {
if (lx + 1 == rx) {
t[x] = val;
return;
}
int mid = (lx + rx) >> 1;
if (i < mid) modify(i, val, x << 1, lx, mid);
else modify(i, val, x << 1 | 1, mid, rx);
pull(x);
}
int query(int l, int r) {
return query(l, r, 1, 0, sz);
}
int query(int l, int r, int x, int lx, int rx) {
if (l >= rx || lx >= r) return 0;
if (l <= lx && rx <= r) return t[x];
int mid = (lx + rx) >> 1;
return max(query(l, r, x << 1, lx, mid), query(l, r, x << 1 | 1, mid, rx));
}
};
int n;
vector<int> x, y;
int prodX = 1;
set<int> alive;
bool operator<(pair<i128, i128> a, pair<i128, i128> b) {
return a.first * b.second < a.second * b.first;
}
segtreeY st;
int answer() {
alive.insert(0);
if (alive.empty()) {
return st.t[1] % MOD;
}
auto it = alive.end();
pair<i128, i128> ans = {0, 1};
i128 prod = 1;
do {
it = prev(it);
pair<i128, i128> now = {st.query(*it, n), prod};
if (ans < now) {
ans = now;
}
prod *= x[*it];
now = {1e9, prod};
if (now < ans) {
break;
}
} while (it != alive.begin());
int val = mul(ans.first % MOD, inv(ans.second % MOD));
return mul(prodX, val);
}
int init(int N, int X[], int Y[]) {
n = N;
x.resize(n), y.resize(n);
for (int i = 0; i < n; ++i) {
x[i] = X[i], y[i] = Y[i];
if (x[i] != 1) {
prodX = mul(prodX, x[i]);
alive.insert(alive.end(), i);
}
}
st.init(y);
return answer();
}
int updateX(int pos, int val) {
prodX = mul(prodX, inv(x[pos]));
x[pos] = val;
prodX = mul(prodX, x[pos]);
if (val == 1) {
alive.erase(pos);
} else {
alive.insert(pos);
}
return answer();
}
int updateY(int pos, int val) {
y[pos] = val;
st.modify(pos, val);
return answer();
}
