#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
// It is always optimal to sell all horses in a single year
class SegmentTree {
private:
struct Mint {
int val = 0;
bool overflow = 0;
const Mint operator * (const Mint &x) const {
return {(int) (1ll * this->val * x.val % mod),
(bool) (this->overflow || x.overflow || (1ll * this->val * x.val >= mod))};
}
};
int sz;
vector<Mint> X;
vector<int> Y;
vector<int> optimal;
void Pull(int n, int lc, int rc) {
Mint in_between = QueryX(1, 0, sz - 1, optimal[lc] + 1, optimal[rc]);
if (in_between.overflow) {
optimal[n] = optimal[rc];
} else if (Y[optimal[lc]] > 1ll * Y[optimal[rc]] * in_between.val) {
optimal[n] = optimal[lc];
} else {
optimal[n] = optimal[rc];
}
}
Mint QueryX(int n, int tl, int tr, int l, int r) {
if (tr < l || r < tl || tl > tr || l > r) return Mint({1, 0});
if (l <= tl && tr <= r) return X[n];
int mid = (tl + tr) / 2;
int z = 2 * (mid - tl + 1);
return QueryX(n + 1, tl, mid, l, r) * QueryX(z, mid + 1, tr, l, r);
}
void UpdateX(int n, int tl, int tr, int p, int x) {
if (tl == tr) {
X[n] = {x, 0};
optimal[n] = tl;
return;
}
int mid = (tl + tr) / 2;
int z = 2 * (mid - tl + 1);
if (p <= mid) {
UpdateX(n + 1, tl, mid, p, x);
} else {
UpdateX(z, mid + 1, tr, p, x);
}
X[n] = X[n + 1] * X[z];
}
void UpdateY(int n, int tl, int tr, int p, int x) {
if (tl == tr) {
Y[tl] = x;
optimal[n] = tl;
return;
}
int mid = (tl + tr) / 2;
int z = 2 * (mid - tl + 1);
if (p <= mid) {
UpdateY(n + 1, tl, mid, p, x);
} else {
UpdateY(z, mid + 1, tr, p, x);
}
Pull(n, n + 1, z);
}
public:
SegmentTree() {}
SegmentTree(int n) : sz(n) {
X.assign(2 * sz, Mint({1, 0}));
Y.assign(sz, 0);
optimal.assign(2 * sz, 0);
}
void UpdateX(int p, int x) {
return UpdateX(1, 0, sz - 1, p, x);
}
void UpdateY(int p, int x) {
return UpdateY(1, 0, sz - 1, p, x);
}
int Query() {
return 1ll * QueryX(1, 0, sz - 1, 0, optimal[1]).val * Y[optimal[1]] % mod;
}
};
SegmentTree segtree;
int init(int N, int X[], int Y[]) {
segtree = SegmentTree(N);
for (int i = 0; i < N; i++) {
segtree.UpdateX(i, X[i]);
segtree.UpdateY(i, Y[i]);
}
return segtree.Query();
}
int updateX(int pos, int val) {
segtree.UpdateX(pos, val);
return segtree.Query();
}
int updateY(int pos, int val) {
segtree.UpdateY(pos, val);
return segtree.Query();
}
