#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int mul(int a, int b) {
if (a > mod / b) {
return mod;
}
else {
return a * b;
}
}
struct node {
int best;
int prod1;
int prod2;
};
const int maxN = 5e5 + 20;
node tree[maxN * 4];
int X[maxN];
int Y[maxN];
int N;
int get(int id, int lt, int rt, int ql, int qr, int type) {
if (lt == ql && rt == qr) {
if (type == 1) {
return tree[id].prod1;
}
else {
return tree[id].prod2;
}
}
int mt = (lt + rt) / 2;
if (qr <= mt) {
return get(id * 2, lt, mt, ql, qr, type);
}
else if (ql >= mt + 1) {
return get(id * 2 + 1, mt + 1, rt, ql, qr, type);
}
else {
if (type == 1) {
return mul(get(id * 2, lt, mt, ql, mt, type), get(id * 2 + 1, mt + 1, rt, mt + 1, qr, type));
}
else {
return 1LL * get(id * 2, lt, mt, ql, mt, type) * get(id * 2 + 1, mt + 1, rt, mt + 1, qr, type) % mod;
}
}
}
void merge(int id, int type) {
if (type == 1) {
tree[id].prod1 = mul(tree[id * 2].prod1, tree[id * 2 + 1].prod1);
tree[id].prod2 = 1LL * tree[id * 2].prod2 * tree[id * 2 + 1].prod2 % mod;
}
else {
int best_l = tree[id * 2].best;
int best_r = tree[id * 2 + 1].best;
if (mul(get(1, 1, N, best_l + 1, best_r, 1), Y[best_r]) > Y[best_l]) {
tree[id].best = best_r;
}
else {
tree[id].best = best_l;
}
}
}
void build(int id, int lt, int rt, int type) {
if (lt == rt) {
if (type == 1) {
tree[id].prod1 = X[lt];
tree[id].prod2 = X[lt];
}
else {
tree[id].best = lt;
}
return;
}
int mt = (lt + rt) / 2;
build(id * 2, lt, mt, type);
build(id * 2 + 1, mt + 1, rt, type);
merge(id, type);
}
void update(int id, int lt, int rt, int pos, int type) {
if (lt == rt) {
if (type == 1) {
tree[id].prod1 = X[lt];
tree[id].prod2 = X[lt];
}
else {
tree[id].best = lt;
}
return;
}
int mt = (lt + rt) / 2;
if (pos <= mt) {
update(id * 2, lt, mt, pos, type);
}
else {
update(id * 2 + 1, mt + 1, rt, pos, type);
}
merge(id, type);
}
int calc() {
return 1LL * get(1, 1, N, 1, tree[1].best, 2) * Y[tree[1].best] % mod;
}
int init(int _N, int _X[], int _Y[]) {
N = _N;
for (int i = 1; i <= N; i++) {
X[i] = _X[i - 1];
Y[i] = _Y[i - 1];
}
build(1, 1, N, 1);
build(1, 1, N, 2);
return calc();
}
int updateX(int pos, int val) {
pos++;
X[pos] = val;
update(1, 1, N, pos, 1);
update(1, 1, N, pos, 2);
return calc();
}
int updateY(int pos, int val) {
pos++;
Y[pos] = val;
update(1, 1, N, pos, 2);
return calc();
}
