#include "horses.h"
#include <limits>
#include <vector>
#include <set>
using namespace std;
using llong = long long;
const llong mod = 1000'000'007;
#define ROOT 1, 0, n - 1
llong Pow(llong a, llong p)
{
if (p == 0) return 1;
if (p % 2) return (a * Pow(a, p - 1)) % mod;
return Pow((a * a) % mod, p / 2);
}
inline llong Inv(llong a) { return Pow(a % mod, mod - 2); }
int n;
vector<int> x, c;
set<int> chng;
llong xmult;
int t[4 * 500'000];
void Set(int v, int vl, int vr, int i, int val)
{
if (vl == vr)
{
t[v] = val;
return;
}
int vm = (vl + vr) / 2;
if (i <= vm) Set(v * 2, vl, vm, i, val);
else Set(v * 2 + 1, vm + 1, vr, i, val);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
int Max(int v, int vl, int vr, int l, int r)
{
if (l > vr || vl > r)
return numeric_limits<int>::min();
if (l <= vl && vr <= r)
return t[v];
int vm = (vl + vr) / 2;
return max(Max(v * 2, vl, vm, l, r), Max(v * 2 + 1, vm + 1, vr, l, r));
}
struct Rat
{
llong a, b;
};
inline bool operator<(Rat l, Rat r) { return l.a * r.b < r.a * l.b; }
int Solve()
{
if (chng.empty())
return Max(ROOT, 0, n - 1);
Rat mx{0, 1};
llong curxmult = 1;
for (auto it = chng.rbegin(); it != chng.rend() && curxmult < 1000'000'000LL; ++it)
{
int i = *it;
int j = (it == chng.rbegin() ? n : *prev(it));
mx = max(mx, Rat{Max(ROOT, i, j - 1), curxmult});
curxmult *= x[i];
}
llong res = (mx.a * Inv(mx.b)) % mod;
return res = (res * xmult) % mod;
}
int init(int N, int X[], int Y[]) {
n = N;
x.assign(X, X + N);
c.assign(Y, Y + N);
chng.clear();
for (int i = 0; i < n; ++i)
Set(ROOT, i, c[i]);
xmult = 1;
for (int i = 0; i < n; ++i)
if (x[i] > 1)
{
chng.insert(i);
xmult = (xmult * x[i]) % mod;
}
return Solve();
}
int updateX(int pos, int val) {
if (x[pos] > 1 && val == 1)
chng.erase(pos);
if (x[pos] == 1 && val > 1)
chng.insert(pos);
xmult = (xmult * Inv(x[pos])) % mod;
xmult = (xmult * (x[pos] = val)) % mod;
return Solve();
}
int updateY(int pos, int val) {
Set(ROOT, pos, c[pos] = val);
return Solve();
}
