#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 val, prod;
double lgprod, lgval; // for comparisons
};
vector<node> tree;
node merge(node &a, node &b) {
node re;
re.prod = (a.prod * b.prod) % MOD;
re.lgprod = a.lgprod + b.lgprod;
if (a.lgval > b.lgval + a.lgprod) {
re.val = a.val;
re.lgval = a.lgval;
} else {
re.val = (b.val * a.prod) % MOD;
re.lgval = b.lgval + a.lgprod;
}
re.val %= MOD;
re.prod %= MOD;
return re;
}
void update(ll p, ll tl = 0, ll tr = N-1, ll i = 1) {
if (tl == tr) {
tree[i].prod = X[tl];
tree[i].val = (tree[i].prod * Y[tl]) % MOD;
tree[i].lgprod = log(tree[i].prod);
tree[i].lgval = log(tree[i].prod) + log(Y[tl]);
return ;
}
ll tm = (tl + tr) / 2;
if (p <= tm) update(p, tl, tm, i * 2);
else update(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);
::X.resize(N), ::Y.resize(N);
for(int i = 0; i < N; i++) {
::X[i] = X[i], ::Y[i] = Y[i];
update(i);
}
return tree[1].val;
}
int updateX(int pos, int val) {
X[pos] = val;
update(pos);
return tree[1].val;
}
int updateY(int pos, int val) {
Y[pos] = val;
update(pos);
return tree[1].val;
}
