#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 5e5 + 5;
const int MAX_K = 50 + 5;
const int MOD = 1e9 + 7;
int _N;
vector<int> _X(MAX_N), _Y(MAX_N);
set<int> non_one;
int mult(int a, int b) {
long long res = 1LL * a * b;
if (res >= MOD) res %= MOD;
return res;
}
class SegmentTree {
private:
struct Node {
int product;
int opt;
Node() {
product = 1;
opt = -1;
}
void merge(Node l, Node r, int rightmost) {
product = mult(l.product, r.product);
opt = l.opt;
assert ( (l.opt == -1 && r.opt == -1) == false );
if (l.opt == -1) {
opt = r.opt;
return;
}
if (r.opt == -1) {
opt = l.opt;
return;
}
auto start_location = non_one.upper_bound(opt);
long long best_multiplier = _Y[opt];
long long road = 1;
for (int i = 0; i < MAX_K && start_location != non_one.end() && *start_location <= r.opt; i++) {
int cur = _X[*start_location];
long long nxt = 1LL * road * cur;
if (nxt >= best_multiplier || (1LL * nxt * _Y[*start_location] >= best_multiplier)) {
opt = r.opt;
return;
}
start_location = next(start_location);
road = nxt;
}
if (1LL * road * _Y[r.opt] >= best_multiplier) {
opt = r.opt;
}
}
};
const int LO, HI;
vector<Node> seg;
void update(int where, int delta, int l, int r, int node) {
if (l > where || r < where) {
return;
}
if (l >= where && r <= where) {
seg[node].opt = l;
seg[node].product = delta;
return;
}
const int mid = l + (r - l) / 2;
update(where, delta, l, mid, 2 * node + 1);
update(where, delta, mid + 1, r, 2 * node + 2);
seg[node].merge(seg[2 * node + 1], seg[2 * node + 2], r);
}
int query(int ql, int qr, int l, int r, int node) {
if (l > qr || r < ql) {
return 1;
}
if (l >= ql && r <= qr) {
return seg[node].product;
}
const int mid = l + (r - l) / 2;
return mult(query(ql, qr, l, mid, 2 * node + 1), query(ql, qr, mid + 1, r, 2 * node + 2));
}
public:
SegmentTree(int n) : LO(0), HI(n - 1) {
seg = vector<Node>(4 * n);
}
void update(int where, int delta) {
update(where, delta, LO, HI, 0);
}
int solve() {
const int optimal_location = seg[0].opt;
return mult( query(0, optimal_location, LO, HI, 0), _Y[optimal_location]);
}
};
SegmentTree seg(MAX_N);
int init(int N, int X[], int Y[]) {
for (int i = 0; i < N; i++) {
_X[i] = X[i];
_Y[i] = Y[i];
if (_X[i] > 1) {
non_one.insert(i);
}
}
for (int i = 0; i < N; i++) {
seg.update(i, _X[i]);
}
return seg.solve();
}
int updateX(int pos, int val) {
if (non_one.find(pos) != non_one.end()) {
non_one.erase(pos);
}
_X[pos] = val;
if (_X[pos] > 1) {
non_one.insert(pos);
}
seg.update(pos, val);
return seg.solve();
}
int updateY(int pos, int val) {
_Y[pos] = val;
seg.update(pos, _X[pos]);
return seg.solve();
}
