#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
#include "horses.h"
const ll MOD = 1e9 + 7;
const ll MAX = 1e9 + 5;
const ll MAX_SZ = 5e5 + 5;
struct Segtree { // point update, range max query
int sz;
vi vals;
void init(int N) {
sz = 1;
while (sz < N)
sz *= 2;
vals = vi(2 * sz, 0);
}
void upd(int pos, ll val, int id, int left, int right) {
if (right - left == 1) {
vals[id] = val;
return;
}
int mid = (left + right) / 2;
if (pos < mid)
upd(pos, val, 2 * id + 1, left, mid);
else
upd(pos, val, 2 * id + 2, mid, right);
vals[id] = max(vals[2 * id + 1], vals[2 * id + 2]);
}
void upd(int pos, ll val) {
upd(pos, val, 0, 0, sz);
}
ll query(int qleft, int qright, int id, int left, int right) {
if (qleft <= left && right <= qright)
return vals[id];
if (qright <= left || right <= qleft)
return 0;
int mid = (left + right) / 2;
ll s1 = query(qleft, qright, 2 * id + 1, left, mid);
ll s2 = query(qleft, qright, 2 * id + 2, mid, right);
return max(s1, s2);
}
ll query(int qleft, int qright) {
return query(qleft, qright, 0, 0, sz);
}
};
ll norm(ll x) {
x %= MOD;
x += MOD;
x %= MOD;
return x;
}
ll binpow(ll x, ll y) {
x = norm(x);
ll res = 1;
while (y > 0) {
if (y % 2 == 1)
res = norm(res * x);
x = norm(x * x);
y /= 2;
}
return res;
}
ll inv(ll x) {
return binpow(x, MOD - 2);
}
int N;
vi X;
vi Y;
Segtree st;
set<int> gp; // pos of X w/ val > 1
ll prodall = 1; // product of all X_i
ll solve() {
auto it = gp.end();
ll currn = Y[N - 1];
ll currd = 1;
ll bestn = currn;
ll bestd = currd;
while (it != gp.begin()) {
it--;
if (currd > MAX)
break;
int p1 = *it;
int p2 = N;
if (it != (--gp.end())) {
auto it2 = it;
it2++;
p2 = *it2;
}
currn = st.query(p1, p2);
// cout<<"at "<<p1<<" "<<p2<<endl;
// cout<<"currn, currd: "<<currn<<" "<<currd<<endl;
if (currn * bestd > bestn * currd) {
bestn = currn;
bestd = currd;
}
currd *= X[*it]; // update denominator
}
// cout<<"bestn, bestd: "<<bestn<<" "<<bestd<<endl;
ll ans = norm(prodall * norm(bestn * inv(bestd)));
return ans;
}
int init(int n, int x[], int y[]) {
N = n;
X = vi(N); Y = vi(N);
for (int i = 0; i < N; i++) {
X[i] = x[i];
Y[i] = y[i];
}
st.init(N);
for (int i = 0; i < N; i++) {
st.upd(i, Y[i]);
}
/* cout<<"st: ";
for (int i = 0; i < st.sz * 2; i++) {
cout<<st.vals[i]<<" ";
}
cout<<endl;*/
for (int i = 0; i < N; i++) {
if (X[i] != 1)
gp.insert(i);
}
gp.insert(-1);
for (int i = 0; i < N; i++) {
prodall *= X[i];
prodall = norm(prodall);
}
ll ans = solve();
return (int)(ans);
}
int updateX(int pos, int val) {
if (X[pos] != 1 && val == 1)
gp.erase(pos);
if (X[pos] == 1 && val != 1)
gp.insert(pos);
prodall = norm(prodall * inv(X[pos]));
X[pos] = val;
prodall = norm(prodall * X[pos]);
ll ans = solve();
return (int)(ans);
}
int updateY(int pos, int val) {
Y[pos] = val;
st.upd(pos, val);
ll ans = solve();
return (int)(ans);
}
