#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
using ll = long long;
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 (long long) a * 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);
}
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, int x = 1, int lx = 0, int rx = sz) {
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, int x = 1, int lx = 0, int rx = sz) {
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;
int answer() {
int maxY = t[1];
if (alive.empty()) {
return maxY;
}
vector<int> pos;
ll m = 1;
auto it = alive.end();
do {
it = prev(it);
m *= x[*it];
} while (m <= maxY && it != alive.begin());
if (m <= maxY) {
vector<int> consider;
for (int i : alive) consider.push_back(i);
if (consider[0] != 0) {
consider.insert(consider.begin(), 0);
}
ll prod = 1;
ll ans = 1;
consider.push_back(n);
for (int i = 0; i < (int) consider.size() - 1; ++i) {
int j = consider[i];
prod *= x[j];
ans = max(ans, prod * query(j, consider[i + 1]));
}
return ans % MOD;
}
ll ans = 1;
auto itt = it;
int newProd = mul(prodX, inv(m / x[*it]));
for (m = 1; it != alive.end(); it = next(it)) {
if (it != itt) {
m *= x[*it];
}
ans = max(ans, m * query(*it, n));
}
ans %= MOD;
return mul(newProd, ans);
}
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);
}
}
init(y);
return answer();
}
int updateX(int pos, int val) {
prodX = mul(prodX, inv(x[pos]));
x[pos] = val;
prodX = mul(prodX, val);
if (val == 1) {
alive.erase(pos);
} else {
alive.insert(pos);
}
return answer();
}
int updateY(int pos, int val) {
y[pos] = val;
modify(pos, val);
return answer();
}
