#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define sep ' '
#define debug(x) cerr << #x << ": " << x << endl;
#define X first
#define Y second
typedef long long ll;
typedef pair<ll, ll> pll;
const ll MAXN = 3e6 + 10;
const ll MOD = 1e9 + 7;
const ll INF = 1e9 + 10;
const ll LOG = 30;
inline ll poww(ll a, ll b) {
ll ans = 1;
while (b) {
if (b & 1) ans = ans * a % MOD;
b >>= 1;
a = a * a % MOD;
}
return ans;
}
inline bool cmp(pll a, pll b) {
return a.X * b.Y > a.Y * b.X;
}
ll X[MAXN], Y[MAXN], n;
namespace segment {
ll sg[MAXN];
void build(int l = 1, int r = n, int v = 1) {
if (l == r) sg[v] = Y[l];
else {
int mid = (l + r) >> 1;
build(l, mid, v << 1);
build(mid + 1, r, v << 1 | 1);
sg[v] = max(sg[v << 1], sg[v << 1 | 1]);
}
}
void update(int ind, int l = 1, int r = n, int v = 1) {
if (l == r) sg[v] = Y[l];
else {
int mid = (l + r) >> 1;
if (ind <= mid) update(ind, l, mid, v << 1);
else update(ind, mid + 1, r, v << 1 | 1);
sg[v] = max(sg[v << 1], sg[v << 1 | 1]);
}
}
ll query(int ql, int qr, int l = 1, int r = n, int v = 1) {
if (ql > r || qr < l) return 0;
if (ql <= l && qr >= r) return sg[v];
int mid = (l + r) >> 1;
return max(query(ql, qr, l, mid, v << 1),
query(ql, qr, mid + 1, r, v << 1 | 1));
}
}
set<int> st;
ll mul = 1;
inline ll solve() {
ll f = 1;
pll best = {Y[n], 1};
int j = 0;
for (auto it = prev(prev(st.end())); j < LOG && f < INF; it--, j++) {
int nxt = *next(it);
int i = *it;
ll mx = segment::query(i, nxt - 1);
if (cmp(pll(mx, f), best)) best = pll(mx, f);
f *= X[i];
if (it == st.begin()) break;
}
return mul * best.X % MOD * poww(best.Y, MOD - 2) % MOD;
}
int init(int N_, int X_[], int Y_[]) {
n = N_;
for (int i = 1; i <= n; i++) {
X[i] = X_[i - 1], Y[i] = Y_[i - 1];
if (X[i] > 1) st.insert(i);
mul = mul * X[i] % MOD;
}
segment::build();
st.insert(1);
st.insert(n + 1);
return solve();
}
int updateX(int pos, int val) {
pos++;
mul = mul * poww(X[pos], MOD - 2) % MOD;
if (pos > 1) {
if (X[pos] > 1 && val == 1) st.erase(pos);
else if (X[pos] == 1 && val > 1) st.insert(pos);
}
X[pos] = val;
mul = mul * X[pos] % MOD;
return solve();
}
int updateY(int pos, int val) {
pos++;
Y[pos] = val;
segment::update(pos);
return solve();
}
