#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
const ll INF = 1e18;
const int LOG = 35;
struct Node {
ll prodX, mxX, mxY;
Node(ll _prodX=1, ll _mxX=-INF, ll _mxY=-INF):
prodX(_prodX), mxX(_mxX), mxY(_mxY) {}
Node operator+(Node right) {
Node left = *this;
return Node(
(left.prodX * right.prodX) % MOD,
max(left.mxX, right.mxX),
max(left.mxY, right.mxY)
);
}
};
struct SEG {
vector<Node> seg; int n;
SEG(int _n=0) {
n = 1;
while (n < _n) n <<= 1;
seg = vector<Node> (2*n);
}
int getLeft(int v) {
return 2*v;
}
int getRight(int v) {
return 2*v+1;
}
void upd(int v, int l, int r, int i, Node val) {
if (l == r) {
seg[v] = val;
return;
}
int m = (l + r) / 2;
if (i <= m) upd(getLeft(v), l, m, i, val);
else upd(getRight(v), m+1, r, i, val);
seg[v] = seg[getLeft(v)] + seg[getRight(v)];
}
Node rng(int v, int l, int r, int a, int b) {
if (a <= l and r <= b) {
return seg[v];
}
if (r < a or b < l) return Node();
int m = (l + r) / 2;
return rng(getLeft(v), l, m, a, b) + rng(getRight(v), m+1, r, a, b);
}
};
int n;
SEG seg;
int getAns() {
ll mxY = 0, mxProdX = 0; int ans = 0;
for (int i=1; i<=min(LOG, n) and mxProdX * mxY <= 1000000000LL; i++) {
Node node = seg.rng(1, 0, seg.n-1, n-i, n-i);
ll x = node.mxX, y = node.mxY;
if (mxProdX * mxY < y) {
mxY = y;
mxProdX = 1;
ans = n-i;
}
mxProdX *= x;
}
return (int)((seg.rng(1, 0, seg.n-1, 0, ans).prodX * mxY) % MOD);
}
int init(int N, int X[], int Y[]) {
n = N;
seg = SEG(n);
for (int i=0; i<n; i++)
seg.upd(1, 0, seg.n-1, i, Node(X[i], X[i], Y[i]));
return getAns();
}
int updateX(int pos, int val) {
Node curr = seg.rng(1, 0, seg.n-1, pos, pos);
curr.mxX = val; curr.prodX = val;
seg.upd(1, 0, seg.n-1, pos, curr);
return getAns();
}
int updateY(int pos, int val) {
Node curr = seg.rng(1, 0, seg.n-1, pos, pos);
curr.mxY = val;
seg.upd(1, 0, seg.n-1, pos, curr);
return getAns();
}
