#include "horses.h"
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long llong;
const int MOD = 1e9 + 7;
class SegmentTreeMax {
int N;
vector<int> A;
vector<int> tree;
void _preprocess(int node, int L, int R);
void _update(int idx, int val, int node, int L, int R);
int _query(int i, int j, int node, int L, int R) const;
public:
void preprocess(const vector<int>& _A) {
A = _A;
N = A.size();
tree = vector<int>(4*N, -1);
_preprocess(1, 0, N-1);
}
void update(int idx, int val) {
_update(idx, val, 1, 0, N-1);
}
int query(int i, int j) const {
return _query(i, j, 1, 0, N-1);
}
};
void SegmentTreeMax::_preprocess(int node, int L, int R) {
if (L == R) {
tree[node] = L;
return;
}
_preprocess(2*node, L, (L+R)/2);
_preprocess(2*node+1, (L+R)/2+1, R);
int pL = tree[2*node], pR = tree[2*node+1];
if (pL < 0)
tree[node] = pR;
else if (pR < 0)
tree[node] = pL;
else
tree[node] = A[pL] >= A[pR] ? pL : pR;
}
void SegmentTreeMax::_update(int idx, int val, int node, int L, int R) {
if (idx < L || idx > R)
return;
if (L == R) {
A[L] = val;
// tree[node] = L;
return;
}
_update(idx, val, 2*node, L, (L+R)/2);
_update(idx, val, 2*node+1, (L+R)/2+1, R);
int pL = tree[2*node], pR = tree[2*node+1];
if (pL < 0)
tree[node] = pR;
else if (pR < 0)
tree[node] = pL;
else
tree[node] = A[pL] >= A[pR] ? pL : pR;
}
int SegmentTreeMax::_query(int i, int j, int node, int L, int R) const {
if (i > R || j < L)
return -1;
if (i <= L && R <= j)
return tree[node];
int pL = _query(i, j, 2*node, L, (L+R)/2);
int pR = _query(i, j, 2*node+1, (L+R)/2+1, R);
if (pL < 0) return pR;
else if (pR < 0) return pL;
else return A[pL] >= A[pR] ? pL : pR;
}
class SegmentTreeMult {
int N;
vector<int> tree;
void _preprocess(const vector<int>& A, int node, int L, int R);
void _update(int idx, int val, int node, int L, int R);
int _query(int i, int j, int node, int L, int R) const;
public:
void preprocess(const vector<int>& A) {
N = A.size();
tree = vector<int>(4*N);
_preprocess(A, 1, 0, N-1);
}
void update(int idx, int val) {
_update(idx, val, 1, 0, N-1);
}
int query(int i, int j) const {
return _query(i, j, 1, 0, N-1);
}
};
void SegmentTreeMult::_preprocess(const vector<int>& A, int node, int L, int R) {
if (L == R) {
tree[node] = A[L];
return;
}
_preprocess(A, 2*node, L, (L+R)/2);
_preprocess(A, 2*node+1, (L+R)/2+1, R);
tree[node] = (tree[2*node] * 1LL * tree[2*node+1]) % MOD;
}
void SegmentTreeMult::_update(int idx, int val, int node, int L, int R) {
if (idx < L || idx > R)
return;
if (L == R) {
tree[node] = val;
return;
}
_update(idx, val, 2*node, L, (L+R)/2);
_update(idx, val, 2*node+1, (L+R)/2+1, R);
tree[node] = (tree[2*node] * 1LL * tree[2*node+1]) % MOD;
}
int SegmentTreeMult::_query(int i, int j, int node, int L, int R) const {
if (i > R || j < L)
return 1;
if (i <= L && R <= j)
return tree[node];
int resL = _query(i, j, 2*node, L, (L+R)/2);
int resR = _query(i, j, 2*node+1, (L+R)/2+1, R);
return (resL * 1LL * resR) % MOD;
}
int N;
vector<int> X, Y;
vector<double> logX, logY;
int query(const set<int, greater<int> >& pos_not_ones,
const SegmentTreeMult& st_mult, const SegmentTreeMax& st_max) {
if (pos_not_ones.empty()) {
return Y[st_max.query(0, N-1)];
}
vector<int> pos;
for (auto it = pos_not_ones.begin(); it != pos_not_ones.end(); ++it) {
pos.push_back(*it);
if (int(pos.size()) >= 30)
break;
}
reverse(pos.begin(), pos.end());
pos.push_back(N);
int best_p = 0, best_y = 0;
double cur_log_prod = 0, best_log_prod = 0;
if (pos.size() < 31) {
int pos_max_y = st_max.query(0, pos[0]-1);
best_log_prod = logY[pos_max_y];
best_p = 0;
best_y = Y[pos_max_y];
}
for (int i = 1; i < (int) pos.size(); ++i) {
int p = pos[i-1];
int q = pos[i];
cur_log_prod += logX[p];
int pos_max_y = st_max.query(p, q-1);
double log_prod = cur_log_prod + logY[pos_max_y];
if (best_log_prod < log_prod) {
best_log_prod = log_prod;
best_p = p;
best_y = Y[pos_max_y];
}
}
int res = (st_mult.query(0, best_p) * 1LL * best_y) % MOD;
return res;
}
set<int, greater<int> > pos_not_ones;
SegmentTreeMult st_mult;
SegmentTreeMax st_max;
int init(int N, int X[], int Y[]) {
::N = N;
::X = vector<int>(X, X+N);
::Y = vector<int>(Y, Y+N);
pos_not_ones.clear();
logX = vector<double>(N);
logY = vector<double>(N);
for (int i = 0; i < N; ++i) {
if (X[i] != 1)
pos_not_ones.insert(i);
logX[i] = log(X[i]);
logY[i] = log(Y[i]);
}
st_mult.preprocess(::X);
st_max.preprocess(::Y);
return query(pos_not_ones, st_mult, st_max);;
}
int updateX(int pos, int val) {
st_mult.update(pos, val);
if (X[pos] == 1 && val > 1)
pos_not_ones.insert(pos);
else if (X[pos] > 1 && val == 1)
pos_not_ones.erase(pos);
X[pos] = val;
logX[pos] = log(val);
return query(pos_not_ones, st_mult, st_max);;
}
int updateY(int pos, int val) {
st_max.update(pos, val);
Y[pos] = val;
logY[pos] = log(val);
return query(pos_not_ones, st_mult, st_max);;
}
