#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 5e5 + 10;
const int MOD = 1e9 + 7;
struct Big {
int curr = 1;
bool big = 0;
};
Big segb[4*MAXN];
int x[MAXN], y[MAXN];
int n;
Big multb(Big a, Big b) {
Big ans;
int x = (a.curr * b.curr);
ans.big = (a.big || b.big);
ans.big |= (x >= MOD);
x %= MOD;
ans.curr = x;
return ans;
}
void buildb(int node, int l, int r) {
if (l == r) {
segb[node].curr = x[l];
segb[node].big = 0;
return;
}
int m = (l + r)/2;
buildb(2*node, l, m);
buildb(2*node + 1, m + 1, r);
segb[node] = multb(segb[2*node], segb[2*node + 1]);
}
void updateb(int node, int l, int r, int po) {
if (l == r) {
segb[node].curr = x[l];
segb[node].big = 0;
return;
}
int m = (l + r)/2;
if (po <= m) updateb(2*node, l, m, po);
else updateb(2*node + 1, m + 1, r, po);
segb[node] = multb(segb[2*node], segb[2*node + 1]);
}
Big queryb(int node, int l, int r, int tl, int tr) {
if ((tl <= l) && (r <= tr)) return segb[node];
if ((r < tl) || (tr < l)) return Big();
int m = (l + r)/2;
return multb(queryb(2*node, l, m, tl, tr), queryb(2*node + 1, m + 1, r, tl, tr));
}
struct Node {
int val = 0, totmult = 1, po = 0;
};
Node merge(Node a, Node b) {
Node ans;
// ok, check which side is better
int l = a.po + 1, r = b.po;
Big isbig = queryb(1, 1, n, l, r);
Big onlyy;
onlyy.curr = y[b.po];
onlyy.big = 0;
isbig = multb(isbig, onlyy);
ans.totmult = ((a.totmult * b.totmult) % MOD);
if (isbig.big || (isbig.curr > y[a.po])) {
ans.po = b.po;
ans.val = ((a.totmult * b.val) % MOD);
return ans;
}
ans.po = a.po;
ans.val = a.val;
return ans;
}
Node seg[4*MAXN];
void build(int node, int l, int r) {
if (l == r) {
seg[node].po = l;
seg[node].val = ((x[l]*y[l]) % MOD);
seg[node].totmult = x[l];
return;
}
int m = (l + r)/2;
build(2*node, l, m);
build(2*node + 1, m + 1, r);
seg[node] = merge(seg[2*node], seg[2*node + 1]);
}
void update(int node, int l, int r, int po) {
if (l == r) {
seg[node].po = l;
seg[node].val = ((x[l]*y[l]) % MOD);
seg[node].totmult = x[l];
return;
}
int m = (l + r)/2;
if (po <= m) update(2*node, l, m, po);
else update(2*node + 1, m + 1, r, po);
seg[node] = merge(seg[2*node], seg[2*node + 1]);
}
int32_t init(int32_t N, int32_t X[], int32_t Y[]) {
n = N;
for (int i = 1; i <= n; i++) x[i] = X[i - 1];
for (int i = 1; i <= n; i++) y[i] = Y[i - 1];
buildb(1, 1, n);
build(1, 1, n);
return seg[1].val;
}
int32_t updateX(int32_t pos, int32_t val) {
pos++;
x[pos] = val;
updateb(1, 1, n, pos);
update(1, 1, n, pos);
return seg[1].val;
}
int32_t updateY(int32_t pos, int32_t val) {
pos++;
y[pos] = val;
update(1, 1, n, pos);
return seg[1].val;
}
