#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll MOD = 1e9 + 7;
ll n;
vector<ll> x,y;
struct Node {
ll mod;
long double log;
};
Node mergeHorses(Node &a, Node &b) {
return {(a.mod * b.mod) % MOD, a.log + b.log};
}
Node merge(Node &a, Node &b, Node &horses) {
long double bLog = horses.log + b.log;
ll bMod = (horses.mod * b.mod) % MOD;
if (a.log > bLog) return a;
else return {bMod, bLog};
}
vector<Node> horses(4 * 500010), segTree(4 * 500010);
void buildHorses(ll curNode, ll leftPointer, ll rightPointer) {
if(leftPointer == rightPointer) horses[curNode] = {x[leftPointer], log(x[leftPointer])};
else {
ll midPointer = (leftPointer + rightPointer)/2;
buildHorses(curNode * 2, leftPointer, midPointer);
buildHorses(curNode * 2 + 1, midPointer + 1, rightPointer);
horses[curNode] = mergeHorses(horses[curNode * 2], horses[curNode * 2 + 1]);
}
}
void updateHorses(ll curNode, ll leftPointer, ll rightPointer, ll pos, ll newVal) {
if(leftPointer == rightPointer && leftPointer == pos) {
horses[curNode] = {newVal, log(newVal)};
x[pos] = newVal;
}
else {
ll midPointer = (leftPointer + rightPointer)/2;
if(midPointer >= pos) updateHorses(curNode * 2, leftPointer, midPointer, pos, newVal);
else updateHorses(curNode * 2 + 1, midPointer + 1, rightPointer, pos, newVal);
horses[curNode] = mergeHorses(horses[curNode * 2], horses[curNode * 2 + 1]);
}
}
Node getHorses(ll curNode, ll leftPointer, ll rightPointer, ll leftBoundary, ll rightBoundary) {
if(leftBoundary > rightBoundary) return {1,0};
if(leftPointer == leftBoundary && rightPointer == rightBoundary) return horses[curNode];
ll midPointer = (leftPointer + rightPointer)/2;
Node left = getHorses(curNode * 2, leftPointer, midPointer, leftBoundary, min(midPointer, rightBoundary));
Node right = getHorses(curNode * 2 + 1, midPointer + 1, rightPointer, max(leftBoundary, midPointer + 1), rightBoundary);
return mergeHorses(left, right);
}
void build(ll curNode, ll leftPointer, ll rightPointer) {
if(leftPointer == rightPointer) segTree[curNode] = {(x[leftPointer] * y[leftPointer]) % MOD, log(x[leftPointer]) + log(y[leftPointer])};
else {
ll midPointer = (leftPointer + rightPointer)/2;
build(curNode * 2, leftPointer, midPointer);
build(curNode * 2 + 1, midPointer + 1, rightPointer);
Node addHorses = getHorses(1, 0, n, leftPointer, midPointer);
segTree[curNode] = merge(segTree[curNode * 2],segTree[curNode * 2 + 1], addHorses);
}
}
void update(ll curNode, ll leftPointer, ll rightPointer, ll pos, ll newVal) {
if(leftPointer == rightPointer && leftPointer == pos) {
segTree[curNode] = {(x[leftPointer] * newVal) % MOD, log(x[leftPointer]) + log(newVal)};
y[pos] = newVal;
}
else {
ll midPointer = (leftPointer + rightPointer)/2;
if(midPointer >= pos) update(curNode * 2, leftPointer, midPointer, pos, newVal);
else update(curNode * 2 + 1, midPointer + 1, rightPointer, pos, newVal);
Node addHorses = getHorses(1, 0, n, leftPointer, midPointer);
segTree[curNode] = merge(segTree[curNode * 2],segTree[curNode * 2 + 1], addHorses);
}
}
int init(int N, int X[], int Y[]) {
n = N - 1;
for (int i = 0; i < N; ++i) {
x.push_back(X[i]);
y.push_back(Y[i]);
}
buildHorses(1, 0, n);
build(1, 0, n);
return segTree[1].mod;
}
int updateX(int pos, int val) {
updateHorses(1, 0, n, pos, val);
update(1, 0, n, pos, y[pos]);
return segTree[1].mod;
}
int updateY(int pos, int val) {
update(1, 0, n, pos, val);
return segTree[1].mod;
}
