/*************************************
* author: marvinthang *
* created: 08.03.2023 15:25:43 *
*************************************/
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
template <class T> T invGeneral(T a, T b) {
a %= b;
if (!a) return b == 1 ? 0 : -1;
T x = invGeneral(b, a);
return x == -1 ? -1 : ((1 - 1LL * b * x) / a + b) % b;
}
const int MOD = 1e9 + 7;
const int MAX = 5e5 + 5;
int N, X[MAX], Y[MAX], bit[MAX], st[MAX << 2];
set <int, greater <int>> pos;
void build(int i, int l, int r) {
if (r - l == 1) {
st[i] = Y[l];
return;
}
int m = l + r >> 1;
build(i << 1, l, m);
build(i << 1 | 1, m, r);
st[i] = max(st[i << 1], st[i << 1 | 1]);
}
void update(int i, int l, int r, int p) {
if (r - l == 1) {
st[i] = Y[l];
return;
}
int m = l + r >> 1;
if (p < m) update(i << 1, l, m, p);
else update(i << 1 | 1, m, r, p);
st[i] = max(st[i << 1], st[i << 1 | 1]);
}
int getMax(int i, int l, int r, int u, int v) {
if (l >= v || r <= u) return 0;
if (u <= l && r <= v) return st[i];
int m = l + r >> 1;
return max(getMax(i << 1, l, m, u, v), getMax(i << 1 | 1, m, r, u, v));
}
void update(int i, int v) {
for (++i; i <= N; i += i & -i) bit[i] = 1LL * bit[i] * v % MOD;
}
int getMul(int i) {
int res = 1;
for (++i; i > 0; i &= i - 1) res = 1LL * res * bit[i] % MOD;
return res;
}
int solve(void) {
int res = -1;
long long cb = 1;
int r = N, ma = 0, mb = 0;
for (int l: pos) {
int ca = getMax(1, 0, N, l, r);
if (1LL * ca * mb >= 1LL * ma * cb) {
res = 1LL * getMul(l) * ca % MOD;
ma = ca; mb = cb;
}
cb *= X[l];
if (cb > MOD) break;
r = l;
}
return res;
}
int init(int n, int x[], int y[]) {
N = n;
fill(bit, bit + N + 1, 1);
REP(i, N) {
X[i] = x[i]; Y[i] = y[i];
if (!i || X[i] != 1) {
update(i, X[i]);
pos.insert(i);
}
}
build(1, 0, N);
return solve();
}
int updateX(int i, int val) {
if (X[i] != 1) {
update(i, invGeneral(X[i], MOD));
pos.erase(i);
}
X[i] = val;
if (!i || X[i] != 1) {
update(i, X[i]);
pos.insert(i);
}
return solve();
}
int updateY(int i, int val) {
Y[i] = val;
update(1, 0, N, i);
return solve();
}
