#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
#include "horses.h"
/*
cur[0] = X[i]
dp[0] = cur[0] * Y[0]
cur[i] *= X[i]
dp[i] = max(dp[i-1], cur[i] * Y[i])
cur[i] = product(all X[j] for j <= i)
optimal to sell everything on one day
query(i, j) = start with one horse at i, how much money can you get at j
v x y
6 2 3
4 1 4
3 3 1
*/
ll N;
vector<ll> X, Y;
struct node {
ll vv, xx, yy;
};
vector<node> tree;
node merge(node &a, node &b) {
node re;
re.xx = (a.xx * b.xx) % MOD;
if (a.yy > b.vv) {
re.vv = a.vv;
re.yy = a.yy;
} else {
re.vv = (b.vv * a.xx) % MOD;
re.yy = b.yy;
}
re.vv %= MOD;
re.xx %= MOD;
re.yy %= MOD;
return re;
}
void update(pair<bool, ll> v, ll p, ll tl = 0, ll tr = N-1, ll i = 1) {
if (tl == tr) {
if (v.first) tree[i].yy = v.second;
else tree[i].xx = v.second;
tree[i].vv = (tree[i].xx * tree[i].yy) % MOD;
return ;
}
ll tm = (tl + tr) / 2;
if (p <= tm) update(v, p, tl, tm, i * 2);
else update(v, p, tm + 1, tr, i * 2 + 1);
tree[i] = merge(tree[i * 2], tree[i * 2 + 1]);
}
int init(int N, int X[], int Y[]) {
::N = N;
tree.resize(N*4);
for(int i = 0; i < N; i++) {
update({false, X[i]}, i);
update({true, Y[i]}, i);
}
return tree[1].vv;
}
int updateX(int pos, int val) {
update({false, val}, pos);
return tree[1].vv;
}
int updateY(int pos, int val) {
update({true, val}, pos);
return tree[1].vv;
}
