#include "horses.h"
#include <bits/stdc++.h>
typedef long double ld;
typedef long long ll;
using namespace std;
const int MAXN = 2e6 + 3e2;
const int MOD = 1000000007;
int X[MAXN], Y[MAXN];
int N;
ll powmod(ll n, ll k){
if (k == 0) return 1;
ll x = powmod(n, k / 2);
x = x * x % MOD;
if (k % 2) x = x * n % MOD;
return x;
}
struct node{
ll mult = 1;
ld mx_sum = 0;
bool isUpdated = false;
ll mult_val = 1;
ld add_val = 0;
node(ll a1, ld a2, bool a3, ll a4, ld a5){
mult = a1;
mx_sum = a2;
isUpdated = a3;
mult_val = a4;
add_val = a5;
}
node(){};
};
ll pref_mult[MAXN];
ld pref_sum[MAXN];
node t[MAXN];
void combine(node &par, node lf, node rg){
if (lf.mx_sum < rg.mx_sum) swap(lf, rg);
par.mx_sum = lf.mx_sum;
par.mult = lf.mult;
}
void build(int v = 1, int tl = 0, int tr = N - 1){
if (tl == tr){
t[v].mult = pref_mult[tl] * Y[tl] % MOD;
t[v].mx_sum = pref_sum[tl] + log2(Y[tl]);
return;
}
int tm = (tl + tr) >> 1;
build(v + v, tl, tm);
build(v + v + 1, tm + 1, tr);
combine(t[v], t[v + v], t[v + v + 1]);
}
void propagate(int v, int tl, int tr){
if (!t[v].isUpdated || tl == tr) return;
int tm = (tl + tr) >> 1;
t[v + v].mult = t[v + v].mult * t[v].mult_val % MOD;
t[v + v].mult_val = t[v + v].mult_val * t[v].mult_val % MOD;
t[v + v + 1].mult = t[v + v + 1].mult * t[v].mult_val % MOD;
t[v + v + 1].mult_val = t[v + v + 1].mult_val * t[v].mult_val % MOD;
t[v + v].mx_sum += t[v].add_val;
t[v + v + 1].mx_sum += t[v].add_val;
t[v + v].add_val += t[v].add_val;
t[v + v + 1].add_val += t[v].add_val;
combine(t[v], t[v + v], t[v + v + 1]);
t[v].isUpdated = false;
t[v + v].isUpdated = t[v + v + 1].isUpdated = true;
}
void update(int l, int r, ll mult, ld add, int v = 1, int tl = 0, int tr = N - 1){
if (l <= tl && tr <= r){
t[v].mx_sum += add;
t[v].add_val += add;
t[v].mult = t[v].mult * mult % MOD;
t[v].mult_val = t[v].mult_val * mult % MOD;
t[v].isUpdated = true;
return;
}
if (tl > r || tr < l) return;
propagate(v, tl, tr);
int tm = (tl + tr) >> 1;
update(l, r, mult, add, v + v, tl, tm);
update(l, r, mult, add, v + v + 1, tm + 1, tr);
combine(t[v], t[v + v], t[v + v + 1]);
}
node get(int l, int r, int v = 1, int tl = 0, int tr = N - 1){
if (l <= tl && tr <= r) return t[v];
if (tl > r || tr < l) return node(0, 0, 0, 0, 0);
propagate(v, tl, tr);
int tm = (tl + tr) >> 1;
node res, lf = get(l, r, v + v, tl, tm), rg = get(l, r, v + v + 1, tm + 1, tr);
combine(res, lf, rg);
return res;
}
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];
pref_mult[i] = (i > 0 ? pref_mult[i - 1] : 1) * X[i] % MOD;
pref_sum[i] = (i > 0 ? pref_sum[i - 1] : 0) + log2(X[i]);
}
build();
return get(0, N - 1).mult;
}
int updateX(int pos, int val) {
ll k = val * powmod(X[pos], MOD - 2) % MOD;
update(pos, N - 1, k, 0);
X[pos] = val;
return get(0, N - 1).mult;
}
int updateY(int pos, int val) {
update(pos, pos, 1, ld(log2(val)) - ld(log2(Y[pos])));
Y[pos] = val;
return get(0, N - 1).mult;
}
