#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const long long lim = 1e9 + 1;
const long long mod = 1e9 + 7;
const int mxN = 5e5 + 10;
int n;
long long aX[mxN], aY[mxN];
long long mul(long long x, long long y) {
return min(x * y, lim);
}
struct Node {
int id;
long long p, s;
long long np, ns;
friend Node operator + (Node a, Node b) {
Node c;
long long suffix = mul(a.s, b.p);
if(aY[a.id] > mul(suffix, aY[b.id])) {
c.id = a.id;
c.p = a.p;
c.s = mul(a.s, mul(b.p, b.s));
c.np = a.np;
c.ns = a.ns * b.np % mod * b.ns % mod;
} else {
c.id = b.id;
c.p = mul(mul(a.p, a.s), b.p);
c.s = b.s;
c.np = a.np * a.ns % mod * b.np % mod;
c.ns = b.ns;
}
return c;
}
} ST[mxN << 2];
void build(int id, int l, int r) {
if(l == r) {
ST[id] = {l, aX[l], 1, aX[l], 1};
return ;
}
int mid = (l + r) / 2;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
ST[id] = ST[id * 2] + ST[id * 2 + 1];
}
void update(int id, int l, int r, int x) {
if(r < x || x < l) return ;
if(l == r) {
ST[id] = {l, aX[l], 1, aX[l], 1};
return ;
}
int mid = (l + r) / 2;
update(id * 2, l, mid, x);
update(id * 2 + 1, mid + 1, r, x);
ST[id] = ST[id * 2] + ST[id * 2 + 1];
}
int init(int N, int X[], int Y[]) {
n = N;
for(int i = 0; i < N; i ++) aX[i] = X[i];
for(int i = 0; i < N; i ++) aY[i] = Y[i];
build(1, 0, N - 1);
return ST[1].np * aY[ST[1].id] % mod;
}
int updateX(int pos, int val) {
aX[pos] = val;
update(1, 0, n - 1, pos);
return ST[1].np * aY[ST[1].id] % mod;
}
int updateY(int pos, int val) {
aY[pos] = val;
update(1, 0, n - 1, pos);
return ST[1].np * aY[ST[1].id] % mod;
}
