#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
const int MAX = 5e5 + 5, MOD = 1e9 + 7;
int n;
pii tree[4 * MAX];
int tree2[4 * MAX];
int x[MAX];
int y[MAX];
pii comb(pii a, pii b){
pii c = {0, 0};
if(a.first) c.first = 1;
if(b.first) c.first = 1;
if(1ll * a.second * b.second > 1e9) c.first = 1;
c.second = (1ll * a.second * b.second) % MOD;
return c;
}
void build(int node, int l, int r){
if(l == r){
tree[node] = {0, x[l]};
return;
}
int mid = (l + r) / 2;
build(2 * node, l, mid);
build(2 * node + 1, mid + 1, r);
tree[node] = comb(tree[2 * node], tree[2 * node + 1]);
}
void updatex(int node, int l, int r, int pos, int val){
if(l == r){
tree[node] = {0, val};
return;
}
int mid = (l + r) / 2;
if(pos <= mid){
updatex(2 * node, l, mid, pos, val);
}
else{
updatex(2 * node + 1, mid + 1, r, pos, val);
}
tree[node] = comb(tree[2 * node], tree[2 * node + 1]);
}
pii mult(int node, int l, int r, int ql, int qr){
if(qr < l || r < ql) return {0, 1};
if(ql <= l && r <= qr) return tree[node];
int mid = (l + r) / 2;
return comb(mult(2 * node, l, mid, ql, qr), mult(2 * node + 1, mid + 1, r, ql, qr));
}
int comb2(int a, int b){
if(b > a) swap(a, b);
pii m = mult(1, 0, n - 1, b + 1, a);
if(m.first) return a;
if(1ll * m.second * y[a] > y[b]) return a;
return b;
}
void build2(int node, int l, int r){
if(l == r){
tree2[node] = l;
return;
}
int mid = (l + r) / 2;
build2(2 * node, l, mid);
build2(2 * node + 1, mid + 1, r);
tree2[node] = comb2(tree2[2 * node], tree2[2 * node + 1]);
}
void updatey(int node, int l, int r, int pos){
if(l == r) return;
int mid = (l + r) / 2;
if(pos <= mid){
updatey(2 * node, l, mid, pos);
}
else{
updatey(2 * node + 1, mid + 1, r, pos);
}
tree2[node] = comb2(tree2[2 * node], tree2[2 * node + 1]);
}
int init(int N, int X[], int Y[]){
n = N;
for(int i = 0; i < n; i++){
x[i] = X[i];
y[i] = Y[i];
}
build(1, 0, n - 1);
build2(1, 0, n - 1);
int id = tree2[1];
return 1ll * mult(1, 0, n - 1, 0, id).second * y[id] % MOD;
}
int updateX(int pos, int val) {
x[pos] = val;
updatex(1, 0, n - 1, pos, val);
updatey(1, 0, n - 1, pos);
int id = tree2[1];
return 1ll * mult(1, 0, n - 1, 0, id).second * y[id] % MOD;
}
int updateY(int pos, int val) {
y[pos] = val;
updatey(1, 0, n - 1, pos);
int id = tree2[1];
return 1ll * mult(1, 0, n - 1, 0, id).second * y[id] % MOD;
}
