#include "horses.h"
#include <vector>
using namespace std;
using ll = long long;
using lll = __int128;
const ll MOD = 1e9 + 7;
struct SegTree
{
int n;
vector<lll> tree, res;
vector<ll> moded;
ll binPow(ll a, ll n)
{
ll res = 1;
while (n)
{
if (n & 1) res = (res * a) % MOD;
a = (a * a) % MOD;
n >>= 1;
}
return res;
}
void build(int v, int l, int r, vector<ll> &x, vector<ll> &y)
{
if (l > r) return;
if (l == r)
{
tree[v] = x[l];
res[v] = x[l] * y[l];
moded[v] = x[l];
return;
}
int m = (l + r) >> 1;
build(v << 1, l, m, x, y);
build(v << 1 | 1, m + 1, r, x, y);
tree[v] = min((lll)1e18 + 1, tree[v << 1] * tree[v << 1 | 1]);
res[v] = max(res[v << 1], res[v << 1 | 1] * tree[v << 1]);
moded[v] = moded[v << 1] * moded[v << 1 | 1] % MOD;
}
SegTree()
{}
SegTree(vector<ll> &x, vector<ll> &y) : n((int)x.size())
{
tree.resize(4 * n + 1);
res.resize(4 * n + 1);
moded.resize(4 * n + 1);
build(1, 0, n - 1, x, y);
}
void updateX(int p, ll val, int v, int l, int r)
{
if (l > r) return;
if (l == r)
{
res[v] = res[v] / tree[v] * val;
moded[v] = moded[v] * binPow(tree[v], MOD - 2) % MOD * val % MOD;
tree[v] = val;
return;
}
int m = (l + r) >> 1;
if (p <= m) updateX(p, val,v << 1, l, m);
else updateX(p, val,v << 1 | 1, m + 1, r);
tree[v] = min((lll)1e18 + 1, tree[v << 1] * tree[v << 1 | 1]);
res[v] = max(res[v << 1], res[v << 1 | 1] * tree[v << 1]);
moded[v] = moded[v << 1] * moded[v << 1 | 1] % MOD;
}
void updateY(int p, ll val, int v, int l, int r)
{
if (l > r) return;
if (l == r)
{
res[v] = val * tree[v];
return;
}
int m = (l + r) >> 1;
if (p <= m) updateY(p, val,v << 1, l, m);
else updateY(p, val,v << 1 | 1, m + 1, r);
res[v] = max(res[v << 1], res[v << 1 | 1] * tree[v << 1]);
}
ll getModed(int a, int b, int v, int l, int r)
{
if (a > r || b < l) return 1;
if (a == l && b == r) return moded[v];
int m = (l + r) >> 1;
return getModed(a, min(b, m), v << 1, l, m) * getModed(max(a, m + 1), b, v << 1 | 1, m + 1, r) % MOD;
}
int search(int v, int l, int r, lll mul = 1)
{
if (mul * tree[v] < 1e9) return -1;
if (l == r) return l;
int m = (l + r) >> 1;
int ret = search(v << 1 | 1, m + 1, r, mul);
if (ret != -1) return ret;
return search(v << 1, l, m, mul * tree[v << 1 | 1]);
}
pair<lll, lll> get(int a, int b, int v, int l, int r, lll mul = 1)
{
if (a > r || b < l) return {0, mul};
if (a == l && b == r) return {mul * res[v], mul * tree[v]};
int m = (l + r) >> 1;
pair<lll, lll> ret1 = get(a, min(b, m), v << 1, l, m, mul);
pair<lll, lll> ret2 = get(max(a, m + 1), b, v << 1 | 1, m + 1, r, ret1.second);
return {max(ret1.first, ret2.first), ret2.second};
}
int get()
{
int ind = max(0, search(1, 0, n - 1));
ll res = 1;
if (ind != 0) res = getModed(0, ind - 1, 1, 0, n - 1);
lll ret = get(ind, n - 1, 1, 0, n - 1).first % MOD;
return (res * ret) % MOD;
}
int update(bool w, int p, ll val)
{
if (w) updateY(p, val, 1, 0, n - 1);
else updateX(p, val, 1, 0, n - 1);
return get();
}
};
vector<ll> pref;
SegTree st;
int init(int n, int X[], int Y[])
{
vector<ll> x(n), y(n);
for (int i = 0; i < n; ++i)
{
x[i] = X[i];
y[i] = Y[i];
}
st = SegTree(x, y);
return st.get();
}
int updateX(int pos, int val)
{
return st.update(0, pos, val);
}
int updateY(int pos, int val)
{
return st.update(1, pos, val);
}
