#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
const int mod = 1e9 + 7;
#define double long double
int n;
int x[N], y[N];
double val[N];
struct SegmentTree {
struct Node {
int pos;
double val, lazy;
};
Node T1[4 * N];
int T2[4 * N];
#define mid ((l + r) >> 1)
Node merge(Node &x, Node &y) {
Node z;
z.lazy = 0;
if (x.val > y.val) {
z.pos = x.pos, z.val = x.val;
}
else {
z.pos = y.pos, z.val = y.val;
}
return z;
}
void build(int i, int l, int r) {
T1[i].lazy = 0;
if (l == r) {
T1[i].pos = l, T2[i] = x[l];
T1[i].val = val[l];
return;
}
build(i << 1, l, mid);
build(i << 1 | 1, mid + 1, r);
T1[i] = merge(T1[i << 1], T1[i << 1 | 1]);
T2[i] = 1LL * T2[i << 1] * T2[i << 1 | 1] % mod;
}
void push(int i, int l, int r) {
T1[i].val += T1[i].lazy;
if (l != r) {
T1[i << 1].lazy += T1[i].lazy;
T1[i << 1 | 1].lazy += T1[i].lazy;
}
T1[i].lazy = 0;
}
void updX(int i, int l, int r, int L, int R, double v) {
push(i, l, r);
if (L > r || l > R) return;
if (L <= l && r <= R) {
T1[i].lazy = v, push(i, l, r); return;
}
updX(i << 1, l, mid, L, R, v);
updX(i << 1 | 1, mid + 1, r, L, R, v);
T1[i] = merge(T1[i << 1], T1[i << 1 | 1]);
}
void updY(int i, int l, int r, int p, int v) {
push(i, l, r);
if (p > r || p < l) return;
if (l == r) {
T1[i].val += log(v) - log(y[p]), y[p] = v;
return;
}
updY(i << 1, l, mid, p, v);
updY(i << 1 | 1, mid + 1, r, p, v);
T1[i] = merge(T1[i << 1], T1[i << 1 | 1]);
}
void updPrd(int i, int l, int r, int p, int v) {
if (l == r) {
T2[i] = x[p] = v; return;
}
if (mid >= p) updPrd(i << 1, l, mid, p, v);
else updPrd(i << 1 | 1, mid + 1, r, p, v);
T2[i] = 1LL * T2[i << 1] * T2[i << 1 | 1] % mod;
}
int getPrd(int i, int l, int r, int L, int R) {
if (l > R || L > r) return 1;
if (L <= l && r <= R) return T2[i];
return 1LL * getPrd(i << 1, l, mid, L, R) * getPrd(i << 1 | 1, mid + 1, r, L, R) % mod;
}
#undef mid
} IT;
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];
}
val[0] = log(x[0]);
for (int i = 1; i < n; ++i) {
val[i] = val[i - 1] + log(x[i]);
}
for (int i = 0; i < n; ++i) {
val[i] += log(y[i]);
}
IT.build(1, 0, n - 1);
int opt = IT.T1[1].pos;
return 1LL * IT.getPrd(1, 0, n - 1, 0, opt) * y[opt] % mod;
}
int updateX(int pos, int val) {
IT.updX(1, 0, n - 1, pos, n - 1, log(val) - log(x[pos]));
IT.updPrd(1, 0, n - 1, pos, val);
int opt = IT.T1[1].pos;
return 1LL * IT.getPrd(1, 0, n - 1, 0, opt) * y[opt] % mod;
}
int updateY(int pos, int val) {
IT.updY(1, 0, n - 1, pos, val);
int opt = IT.T1[1].pos;
return 1LL * IT.getPrd(1, 0, n - 1, 0, opt) * y[opt] % mod;
}
