#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
const int mod = 1e9 + 7;
vector <long long> x1, yy;
int n;
struct stree {
vector <long double> logs, full;//logs = logarithm, full = logarithm of 1 -> id.
vector <long long> xx, y, st;//x, y == x, y. st = final ans.
void rs(int size) {
st.resize(4 * size, 0);
xx.resize(4 * size, 0);
y.resize(4 * size, 0);
logs.resize(4 * size, 0.0);
full.resize(4 * size, 0.0);
}
void merge(int id, int x, int y, int l, int r) {
int m = (l + r) / 2;
xx[id] = (xx[x] * xx[y]) % mod;
logs[id] = logs[x] + logs[y];
if (full[x] > logs[x] + full[y]) {
st[id] = st[x];
full[id] = full[x];
}
else {
st[id] = xx[x] * st[y];
st[id] %= mod;
full[id] = logs[x] + full[y];
}
}
void build(int id, int l, int r) {
if (l == r) {
xx[id] = x1[l];
y[id] = yy[l];
st[id] = xx[id] * y[id];
st[id] %= mod;
logs[id] = log2(xx[id]);
full[id] = log2(y[id]) + logs[id];
return;
}
int m = (l + r) / 2, x = id * 2 + 1, y = x + 1;
build(x, l, m);
build(y, m + 1, r);
merge(id, x, y, l, r);
}
void updatex(int id, int l, int r, int i, int k) {
if (l == r) {
xx[id] = k;
st[id] = xx[id] * y[id];
st[id] %= mod;
logs[id] = log2(xx[id]);
full[id] = log2(y[id]) + logs[id];
return;
}
int m = (l + r) / 2, x = 2 * id + 1, y = x + 1;
if (i <= m) {
updatex(x, l, m, i, k);
}
else {
updatex(y, m + 1, r, i, k);
}
merge(id, x, y, l, r);
}
void updatey(int id, int l, int r, int i, int k) {
if (l == r) {
y[id] = k;
st[id] = xx[id] * y[id];
st[id] %= mod;
full[id] = log2(y[id]) + logs[id];
return;
}
int m = (l + r) / 2, x = 2 * id + 1, y = x + 1;
if (i <= m) {
updatey(x, l, m, i, k);
}
else {
updatey(y, m + 1, r, i, k);
}
merge(id, x, y, l, r);
}
};
stree st;
int init(int N, int X[], int Y[]) {
n = N;
x1.resize(n);
yy.resize(n);
st.rs(N);
for (int i = 0;i < n;i++) {
x1[i] = X[i];
yy[i] = Y[i];
}
st.build(0, 0, n - 1);
// cout << st.xx[0] << ' ' << st.y[0] << ' ' << st.st[0] << ' ' << st.logs[0] << ' ' << st.full[0] << endl;
return st.st[0];
}
int updateX(int pos, int val) {
st.updatex(0, 0, n - 1, pos, val);
// cout << st.xx[0] << ' ' << st.y[0] << ' ' << st.st[0] << ' ' << st.logs[0] << ' ' << st.full[0] << endl;
return st.st[0];
}
int updateY(int pos, int val) {
st.updatey(0, 0, n - 1, pos, val);
// cout << st.xx[0] << ' ' << st.y[0] << ' ' << st.st[0] << ' ' << st.logs[0] << ' ' << st.full[0] << endl;
return st.st[0];
}
