#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
const int _N = 5e5 + 7, mod = 1e9 + 7;
const ll inf = 2e18;
int n, m;
ll X[_N], Y[_N];
ll bit[_N];
double bit2[_N];
set<int> st;
pii tree[_N * 4];
ll a42 = 1ll;
void update(int node, int L, int R, int ix, int val)
{
if (L == R)
{
tree[node] = {val, ix - 1};
return;
}
int mid = (L + R) >> 1;
if (ix <= mid)
update(node * 2 + 1, L, mid, ix, val);
else
update(node * 2 + 2, mid + 1, R, ix, val);
tree[node] = max(tree[node * 2 + 1], tree[node * 2 + 2]);
}
pii query(int node, int L, int R, int l, int r)
{
if (l > r || l > R || r < L)
return {-1, -1};
if (L >= l && R <= r)
return tree[node];
int mid = (L + R) >> 1;
pii s1 = query(node * 2 + 1, L, mid, l, r);
pii s2 = query(node * 2 + 2, mid + 1, R, l, r);
return max(s1, s2);
}
inline ll mul(ll x, ll y) { return 1ll * (x % mod) * (y % mod) % mod; }
ll faspow(ll x, ll y)
{
if (!y)
return 1ll;
ll ret = faspow(x, y / 2);
ret = 1ll * ret * ret % mod;
if (y & 1)
ret = 1ll * ret * x % mod;
return ret;
}
inline ll inv(ll x) { return faspow(x, mod - 2); }
inline ll add(ll x, ll y) { return (x + y >= mod ? x + y - mod : x + y); }
void add(int x, ll v, ll old = 1ll)
{
++x;
ll nv = mul(v, inv(old));
a42 = mul(a42, nv);
for (; x < _N; x += x & -x)
bit[x] = mul(bit[x], nv);
}
ll eval(int x)
{
++x;
ll ret = 1ll;
for (; x; x -= x & -x)
ret = 1ll * ret * bit[x] % mod;
return ret;
}
void add2(int pos, double v)
{
++pos;
for (; pos < _N; pos += pos & -pos)
bit2[pos] += v;
}
double get2(int pos)
{
++pos;
double ret = 0;
for (; pos; pos -= pos & -pos)
ret += bit2[pos];
return ret;
}
ll solve()
{
double tot = 0;
double mx = 0;
int k = 0;
int de = n - 1;
double lg = 0;
vector<int> indi;
ll rem = 1ll;
if (st.size())
{
auto it = st.end();
--it;
int sz = (int)st.size();
while (sz--)
{
lg += log(X[(*it)]);
de = (*it);
if (de)
rem = mul(rem, inv(X[*it]));
if (de)
indi.push_back(*it);
if (lg > log(1e9))
break;
--it;
}
if (lg <= log(1e9))
de = 0;
}
else
{
de = 0;
}
indi.push_back(0);
rem = mul(rem, inv(X[0]));
tot = get2(de - 1);
int las = n + 1;
ll now = mul(a42, rem);
ll ret = 1ll;
for (int x = indi.size() - 1; ~x; --x)
{
int u = indi[x];
tot += log(X[u]);
now = mul(now, X[u]);
pii gmax = query(0, 1, _N, u + 1, n);
if (tot + log(gmax.first) > mx)
{
ret = mul(mul(now, a42), mul(rem, Y[gmax.second]));
mx = tot + log(gmax.first);
k = gmax.second;
}
}
return ret;
}
void putit(int x, int val)
{
if (val > 1)
st.insert(x);
else
{
st.erase(x);
}
}
int init(int N, int _X[], int _Y[])
{
n = N;
fill(bit, bit + _N, 1);
for (int i = 0; i < N; ++i)
{
add(i, _X[i]);
add2(i, _X[i]);
putit(i, _X[i]);
update(0, 1, _N, i + 1, _Y[i]);
X[i] = _X[i];
Y[i] = _Y[i];
}
return solve();
}
int updateX(int pos, int val)
{
add(pos, val, X[pos]);
add2(pos, log(val) - log(X[pos]));
putit(pos, val);
X[pos] = val;
return solve();
}
int updateY(int pos, int val)
{
Y[pos] = val;
update(0, 1, _N, pos + 1, val);
return solve();
}
