#include <bits/stdc++.h>
#define int long long
#include "horses.h"
using namespace std;
int aint[2000005];
const int mod = 1e9 + 7;
int n;
int x[500005], y[500005];
int prod = 1;
set<int> s;
int put(int n, int k)
{
if(k == 0) return 1;
if(k % 2 == 1) return put(n * n % mod, k / 2) * n % mod;
return put(n * n % mod, k / 2);
}
void build(int nod, int st, int dr)
{
if(st == dr)
{
aint[nod] = y[st];
return;
}
int mij = (st + dr) / 2;
build(nod * 2, st, mij);
build(nod * 2 + 1, mij + 1, dr);
aint[nod] = max(aint[nod * 2], aint[nod * 2 + 1]);
}
void update(int nod, int st, int dr, int poz, int val)
{
if(st == dr)
{
aint[nod] = val;
return;
}
int mij = (st + dr) / 2;
update(nod * 2, st, mij, poz, val);
update(nod * 2 + 1, mij + 1, dr, poz, val);
aint[nod] = max(aint[nod * 2], aint[nod * 2 + 1]);
}
int query(int nod, int st, int dr, int le, int ri)
{
if(le > ri) return 0;
if(st == le && dr == ri)
return aint[nod];
int mij = (st + dr) / 2;
return max(query(nod * 2, st, mij, le, min(ri, mij)),
query(nod * 2 + 1, mij + 1, dr, max(le, mij + 1), ri));
}
int inv(int x)
{
return put(x, mod - 2);
}
int32_t solve()
{
auto it = s.end();
int currprod = 1, rez = x[1] * y[1];
vector<int> p;
while(1)
{
if(it != s.end() && *it == 0)
break;
it = prev(it);
int i = *it;
assert(x[i] > 1 || i == 0);
if(currprod > 1000000000)
break;
p.push_back(i);
currprod *= x[i];
}
currprod /= x[p.back()];
reverse(p.begin(), p.end());
int prodpref = 1;
for(auto i : p)
{
if(i != p[0])
prodpref *= x[i];
int by = query(1, 1, n, max(i, 1LL), n);
rez = max(rez, by * prodpref);
}
rez %= mod;
return (int32_t)((int)(prod * inv(currprod) % mod * (rez % mod) % mod));
}
int32_t updateX(int32_t poz, int32_t val)
{
poz++;
prod = prod * inv(x[poz]) % mod;
prod = prod * val % mod;
if(x[poz] == 1)
{
if(val > 1)
{
s.insert(poz);
}
}
else
{
if(val == 1)
s.erase(s.find(poz));
}
x[poz] = val;
return solve();
}
int32_t updateY(int32_t poz, int32_t val)
{
poz++;
y[poz] = val;
update(1, 1, n, poz, val);
return solve();
}
int32_t init(int32_t N, int32_t X[], int32_t Y[])
{
n = N;
s.clear();
for(int i = 0; i < n; i++)
{
x[i + 1] = X[i];
y[i + 1] = Y[i];
prod = prod * x[i + 1] % mod;
if(x[i + 1] > 1)
s.insert(i + 1);
}
prod = 1;
x[0] = 1;
y[0] = 1;
s.insert(0);
build(1, 1, n);
return solve();
}
