#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
#define int long long
const int MOD = 1e9 + 7;
struct SegmentTreeMax {
vector<int> S;
int len = 1;
SegmentTreeMax(int n) {
while (len < n) len <<= 1;
S.resize(2 * len);
}
SegmentTreeMax() {}
int query(int ql, int qr, int l = 0, int r = -1, int i = 1) {
if (r == -1) r = len;
if (qr <= l || r <= ql) return 0;
if (ql <= l && r <= qr) return S[i];
int m = (l + r) / 2;
return max(query(ql, qr, l, m, i * 2), query(ql, qr, m, r, i * 2 + 1));
}
void upd(int pos, int val) {
pos += len;
S[pos] = val;
for (pos /= 2; pos > 0; pos /= 2) {
S[pos] = max(S[pos * 2], S[pos * 2 + 1]);
}
}
};
int n;
vector<int> X;
vector<int> Y;
SegmentTreeMax segY;
int solve() {
int prod = 1;
int res = 0;
for (int i = 0; i < n; i++) {
prod = (prod * X[i]) % MOD;
int coef = segY.query(i, n); // max Y[j] where j >= i
res = max(res, (prod * coef) % MOD);
}
return res;
}
int32_t init(int32_t N, int32_t mult[], int32_t cost[]) {
n = N;
X = vector<int>(n);
Y = vector<int>(n);
segY = SegmentTreeMax(n);
for (int i = 0; i < n; i++) {
X[i] = mult[i];
Y[i] = cost[i];
segY.upd(i, Y[i]);
}
return solve();
}
int32_t updateX(int32_t pos, int32_t val) {
X[pos] = val;
return solve();
}
int32_t updateY(int32_t pos, int32_t val) {
Y[pos] = val;
segY.upd(pos, val);
return solve();
}
