#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//#define int ll
using P = pair<int, int>;
#define all(x) x.begin(), x.end()
#define rep(i, l, n) for (int i = l; i < (n); ++i)
#define sz(x) (int)x.size()
const char nl = '\n';
const ll mod = 1e9+7;
//const ll inf = 1e9+1;
struct segtree {
vector<ll> tree;
int size;
void init(int n) {
size = 1;
while (size < n)size <<= 1;
tree.assign(2*size-1, 0);
}
void set(int i, int v, int x, int lx, int rx) {
if (rx-lx == 1) {
tree[x] = v;
return;
}
int mid = lx+rx>>1;
if(i<mid)set(i, v, 2*x+1, lx, mid);
else set(i, v, 2*x+2, mid, rx);
tree[x] = tree[2*x+1]*tree[2*x+2]%mod;
}
void set(int i, int v) {
set(i, v, 0, 0, size);
}
int get(int r, int x, int lx, int rx) {
if (r <= lx)return 1ll;
if (rx <= r)return tree[x];
int mid = lx+rx>>1;
ll p1 = get(r, 2*x+1, lx, mid);
ll p2 = get(r, 2*x+2, mid, rx);
ll j = p1*p2%mod;
return j;
}
int get(int r) {
return get(r, 0, 0, size);
}
};
struct mxtree {
vector<int> tree;
int size;
void init(int n) {
size = 1;
while (size < n)size <<= 1;
tree.assign(2*size-1, 0);
}
void set(int i, int v, int x, int lx, int rx) {
if (rx-lx==1) {
tree[x] = v;
return;
}
int mid = lx+rx>>1;
if(i<mid)set(i,v,2*x+1, lx,mid);
else set(i, v, 2*x+2, mid, rx);
tree[x] = max(tree[2*x+1], tree[2*x+2]);
}
void set(int i, int v) {
set(i, v, 0, 0, size);
}
int get(int l, int r, int x, int lx, int rx) {
if (rx <= l || r <= lx)return 0;
if (l <= lx && rx <= r)return tree[x];
int mid = lx+rx>>1;
return max(get(l, r, 2*x+1, lx, mid),
get(l, r, 2*x+2, mid, rx));
}
int get(int l, int r) {
return get(l, r, 0, 0, size);
}
};
int n;
vector<ll> x, y;
multiset<ll> b, nb;
segtree st;
mxtree yt;
int init(int N, int X[], int Y[]) {
n = N;
rep(i, 0, n)
x.push_back(X[i]),
y.push_back(Y[i]);
st.init(n);
yt.init(n);
ll res = 0, pp = 1;
bool ok = false;
rep(i, 0, n) {
yt.set(i, y[i]);
if (!ok) {
pp *= x[i];
if (pp >= (ll)1e9)ok = true;
}
st.set(i, x[i]);
if (x[i]-1)nb.insert(i);
else b.insert(i);
}
if (!ok)res = yt.tree[0];
if (nb.empty())return res;
//cout << res << nl;
vector<ll> c;
auto it = --nb.end();
int cnt = 0;
while (cnt < 30) {
c.push_back(*it);
if (it == nb.begin())break;
it--, cnt += 1;
}
reverse(all(c));
c.push_back(c.back()+1);
//for (auto i: c)cout << i << " ";
//cout << nl;
ll yp = 0, pr = 1;
if (c[0])yp = yt.get(0, c[0]);
rep(i, 0, sz(c)-1) {
pr = min(mod, pr*x[i]);
int mx = yt.get(c[i], c[i+1]);
if (pr*mx > yp) {
res = st.get(c[i]+1)*mx%mod;
yp = mx, pr = 1;
}
}
return res;
}
int updateX(int pos, int val) {
return 0;
}
int updateY(int pos, int val) {
return 0;
}
