#include <bits/stdc++.h>
#define int long long
#include "horses.h"
using namespace std;
int aint[2000005];
const int mod = 1e9 + 7;
int aib[500005], 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 pasi = 31, last = n, currprod = 1, rez = -1, prd = -1;
while(pasi--)
{
if(*it == 0)
break;
it = prev(it);
int i = *it;
if(currprod >= 1000000000)
break;
int by = query(1, 1, n, max(1LL, i), last);
if(rez == -1) rez = i, prd = currprod;
else
{
int prefprod = prod * inv(currprod) % mod;
int prefrezprod = prod * inv(prd) % mod;
prefrezprod = prefrezprod * inv(prefprod) % mod;
if(prefrezprod * y[rez] < by)
rez = i, prd = currprod;
}
currprod = currprod * x[i];
}
return prod * inv(prd) % mod * y[rez] % 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);
x[poz] = val;
}
}
else
{
if(val == 1)
s.erase(poz);
x[poz] = val;
}
return solve();
}
int32_t updateY(int32_t poz, int32_t val)
{
poz++;
update(1, 1, n, poz, val);
return solve();
}
int32_t init(int32_t N, int32_t X[], int32_t Y[])
{
n = N;
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);
}
x[0] = 1;
y[0] = 1;
s.insert(0);
build(1, 1, n);
return solve();
}
