#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
set<int> xge2;
const int MOD = 1e9 + 7;
const int MX = 5e5 + 5;
struct ST
{
int size;
vector<ll> mul, mx;
ST(int _size) : size(_size), mul(2 * _size, 1), mx(2 * _size) {}
ll qmx(int l, int r)
{
ll ret = 0;
for (l += size, r += size; l < r; l /= 2, r /= 2)
{
if (l & 1)
ret = max(ret, mx[l++]);
if (r & 1)
ret = max(ret, mx[--r]);
}
return ret;
}
ll qmul(int l, int r)
{
ll ret = 1;
for (l += size, r += size; l < r; l /= 2, r /= 2)
{
if (l & 1)
ret = (ret * mul[l++]) % MOD;
if (r & 1)
ret = (ret * mul[--r]) % MOD;
}
return ret;
}
void umx(int i, ll v)
{
mx[i += size] = v;
for (i /= 2; i; i /= 2)
mx[i] = max(mx[2 * i], mx[2 * i + 1]);
}
void umul(int i, ll v)
{
mul[i += size] = v;
for (i /= 2; i; i /= 2)
mul[i] = (mul[2 * i] * mul[2 * i + 1]) % MOD;
}
} st(2 * MX);
int n, x[MX], y[MX];
int ans()
{
if (xge2.empty())
{
return st.qmx(0, n);
}
ll s = 1;
int hi = n;
auto it = xge2.rbegin();
vector<ll> a, b, c;
while (it != xge2.rend())
{
int v = *it;
a.push_back(v);
b.push_back(s);
c.push_back(st.qmx(v, hi));
if (s > MOD)
break;
s *= x[v];
hi = v;
it++;
}
pair<ll, int> mx_ans = {-1, -1};
for (int i = 0; i < (int)a.size(); i++)
{
mx_ans = max(mx_ans, {s / b[i] * c[i], i});
}
ll ans = 0;
ans = (st.qmul(0, a[mx_ans.second] + 1) * c[mx_ans.second]) % MOD;
return ans;
}
int init(int N, int X[], int Y[])
{
n = N;
x[N] = 1;
for (int i = 0; i < N; ++i)
{
if (X[i] >= 2)
xge2.insert(i);
st.umul(i, X[i]);
st.umx(i, Y[i]);
}
copy(X, X + N, x);
copy(Y, Y + N, y);
return ans();
}
int updateX(int pos, int val)
{
if (val == 1 && xge2.find(pos) != xge2.end())
xge2.erase(pos);
else
xge2.insert(pos);
st.umul(pos, x[pos] = val);
return ans();
}
int updateY(int pos, int val)
{
st.umx(pos, y[pos] = val);
return ans();
}
