#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 3;
const int mod = 1e9 + 7;
int n, x[maxn], y[maxn];
set <int> s;
pair <int, int> tr[maxn * 4];
void merge(int v)
{
tr[v].first = max(tr[v * 2].first, tr[v * 2 + 1].first);
tr[v].second = 1ll * tr[v * 2].second * tr[v * 2 + 1].second % mod;
}
void build(int v, int l, int r)
{
if (l == r)
{
tr[v] = {y[l], x[l]};
return;
}
int mid = (l + r) / 2;
build(v * 2, l, mid);
build(v * 2 + 1, mid + 1, r);
merge(v);
}
int get1(int v, int l, int r, int ll, int rr)
{
if (l > rr || r < ll)
return -1;
if (l >= ll && r <= rr)
return tr[v].first;
int mid = (l + r) / 2;
return max(get1(v * 2, l, mid, ll, rr), get1(v * 2 + 1, mid + 1, r, ll, rr));
}
int get2(int v, int l, int r, int ll, int rr)
{
if (l > rr || r < ll)
return 1;
if (l >= ll && r <= rr)
return tr[v].second;
int mid = (l + r) / 2;
return 1ll * get2(v * 2, l, mid, ll, rr) * get2(v * 2 + 1, mid + 1, r, ll, rr) % mod;
}
void update1(int v, int l, int r, int pos, int val)
{
if (l == r)
{
tr[v].first = val;
return;
}
int mid = (l + r) / 2;
if (pos <= mid)
update1(v * 2, l, mid, pos, val);
else
update1(v * 2 + 1, mid + 1, r, pos, val);
merge(v);
}
void update2(int v, int l, int r, int pos, int val)
{
if (l == r)
{
tr[v].second = val;
return;
}
int mid = (l + r) / 2;
if (pos <= mid)
update2(v * 2, l, mid, pos, val);
else
update2(v * 2 + 1, mid + 1, r, pos, val);
merge(v);
}
int get()
{
if (s.empty())
return get1(1, 1, n, 1, n);
else
{
long long pr = 1;
auto it = prev(s.end());
while (it != s.begin() && pr <= 1000000000)
{
pr *= x[*it];
it--;
}
if (it != s.begin() || pr >= 1000000000)
it++;
int to_mult = get2(1, 1, n, 1, *it);
auto it1 = it;
pr = 1;
long long ans = -1;
while (it != s.end())
{
ans = max(ans, pr * y[*it]);
int l = *it + 1, r;
if (it != prev(s.end()))
r = *next(it) - 1;
else
r = n;
if (l <= r)
ans = max(ans, pr * get1(1, 1, n, l, r));
it++;
if (it != s.end())
pr *= x[*it];
}
if (it1 == s.begin() && *it1 != 1)
{
if (pr * x[*it1] <= 1000000000)
{
auto curr = get1(1, 1, n, 1, *it1 - 1);
if (curr / x[*it1] >= ans)
return curr;
}
}
return 1ll * (ans % mod) * to_mult % 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];
build(1, 1, n);
for (int i = 1; i <= n; i++)
if (x[i] != 1)
s.insert(i);
return get();
}
int updateX(int pos, int val)
{
pos++;
if (x[pos] == val)
return get();
update2(1, 1, n, pos, val);
if (val == 1)
s.erase(pos);
else
if (x[pos] == 1)
s.insert(pos);
x[pos] = val;
return get();
}
int updateY(int pos, int val)
{
pos++;
y[pos] = val;
update1(1, 1, n, pos, val);
return get();
}
/*
int n2, q, x2[maxn], y2[maxn];
int main()
{
cin >> n2;
for (int i = 0; i < n2; i++)
cin >> x2[i];
for (int i = 0; i < n2; i++)
cin >> y2[i];
cout << init(n2, x2, y2) << endl;
cin >> q;
while (q--)
{
int type, pos, val;
cin >> type >> pos >> val;
if (type == 1)
cout << updateX(pos, val) << endl;
else
cout << updateY(pos, val) << endl;
}
}
*/
