#include "horses.h"
#include <math.h>
#define MAXN 500000
#define MOD 1000000007
int lgpow(int a, int n) {
int r = 1;
while(n > 0) {
if(n % 2) {
r = 1LL * r * a % MOD;
}
a = 1LL * a * a % MOD;
n /= 2;
}
return r;
}
struct Numar {
double ln;
int val;
Numar(int _val) {
val = _val % MOD;
ln = log(val);
}
Numar() {}
inline Numar operator *(Numar oth) {
Numar ret;
ret.val = 1LL * val * oth.val % MOD;
ret.ln = ln + oth.ln;
return ret;
}
inline Numar operator /(Numar oth) {
Numar ret;
ret.val = 1LL * ret.val * lgpow(oth.val, MOD - 2) % MOD;
ret.ln = ln - oth.ln;
return ret;
}
inline bool operator <(Numar oth) {
return ln < oth.ln;
}
};
static inline Numar max(Numar a, Numar b) {
return a < b ? b : a;
}
Numar aint[4 * MAXN], lazy[4 * MAXN], qval;
int n, x[MAXN], y[MAXN], qleft, qright;
void propagate(int node, int left, int right) {
aint[node] = aint[node] * lazy[node];
if(left < right) {
lazy[2 * node + 1] = lazy[2 * node + 1] * lazy[node];
lazy[2 * node + 2] = lazy[2 * node + 2] * lazy[node];
}
lazy[node] = Numar(1);
}
void _update(int node, int left, int right) {
int middle;
propagate(node, left, right);
if(qleft <= left && right <= qright) {
lazy[node] = lazy[node] * qval;
propagate(node, left, right);
} else {
middle = (left + right) / 2;
propagate(2 * node + 1, left, middle);
propagate(2 * node + 2, middle + 1, right);
if(qleft <= middle) {
_update(2 * node + 1, left, middle);
}
if(middle < qright) {
_update(2 * node + 2, middle + 1, right);
}
aint[node] = max(aint[2 * node + 1], aint[2 * node + 2]);
}
}
void update(int _qleft, int _qright, Numar _qval) {
qleft = _qleft;
qright = _qright;
qval = _qval;
_update(0, 0, n - 1);
}
Numar _query(int node, int left, int right) {
int middle;
Numar ans;
propagate(node, left, right);
if(qleft <= left && right <= qright) {
return aint[node];
}
middle = (left + right) / 2;
ans = Numar(1);
if(qleft <= middle) {
ans = max(ans, _query(2 * node + 1, left, middle));
}
if(middle < qright) {
ans = max(ans, _query(2 * node + 2, middle + 1, right));
}
return ans;
}
Numar query(int _qleft, int _qright) {
qleft = _qleft;
qright = _qright;
return _query(0, 0, n - 1);
}
int init(int _n, int _x[], int _y[]) {
int i;
n = _n;
for(i = 0; i < 4 * n; i++) {
aint[i] = lazy[i] = Numar(1);
}
for(i = 0; i < n; i++) {
x[i] = _x[i];
update(i, n - 1, Numar(x[i]));
y[i] = _y[i];
update(i, i, Numar(y[i]));
}
return query(0, n - 1).val;
}
int updateX(int pos, int val) {
update(pos, n - 1, Numar(val) / Numar(x[pos]));
x[pos] = val;
return query(0, n - 1).val;
}
int updateY(int pos, int val) {
update(pos, pos, Numar(val) / Numar(y[pos]));
y[pos] = val;
return query(0, n - 1).val;
}
