#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
#define ll long long
#define int ll
#define fi first
#define se second
#define ld long double
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
static const int mod = 1e9 + 7;
int pot(int a, int b) {
if (b == 0) return 1;
int x = pot(a, b / 2);
if (b % 2) return x * x % mod * a % mod;
return x * x % mod;
}
struct segment {
static const int dim = 1 << 19;
struct node {
double log = 0;
int mod = 1;
double lazy_log = 0;
int lazy_mod = 1;
};
vector<node> s = vector<node>(2 * dim);
void prop(int pos) {
if (s[pos].lazy_log != 0) {
s[pos].log += s[pos].lazy_log;
if (pos < dim) {
s[2 * pos].lazy_log += s[pos].lazy_log;
s[2 * pos + 1].lazy_log += s[pos].lazy_log;
}
s[pos].lazy_log = 0;
}
if (s[pos].lazy_mod > 1) {
s[pos].mod = s[pos].mod * s[pos].lazy_mod % mod;
if (pos < dim) {
s[2 * pos].lazy_mod = s[2 * pos].lazy_mod * s[pos].lazy_mod % mod;
s[2 * pos + 1].lazy_mod = s[2 * pos + 1].lazy_mod * s[pos].lazy_mod % mod;
}
s[pos].lazy_mod = 1;
}
}
void upd(int pos, int l, int r, int a, int b, double log_, int mod_) {
prop(pos);
if (b < l || r < a) return;
if (a <= l && r <= b) {
s[pos].lazy_log += log_;
s[pos].lazy_mod = s[pos].lazy_mod * mod_ % mod;
prop(pos);
return;
}
int m = (l + r) / 2;
upd(2 * pos, l, m, a, b, log_, mod_);
upd(2 * pos + 1, m + 1, r, a, b, log_, mod_);
if (s[2 * pos].log > s[2 * pos + 1].log)
s[pos] = s[2 * pos];
else
s[pos] = s[2 * pos + 1];
}
void upd(int a, int b, double log_, int mod_) {
upd(1, 0, dim - 1, a, b, log_, mod_);
}
int query() {
prop(1);
// cout << s[1].log << " " << s[1].lazy_mod << " " << s[1].lazy_log << endl;
return s[1].mod;
}
} seg;
vector<int> X, Y;
int N;
int calc() {
int ma = 0;
int cur = 1;
for (int i = 0; i < N; i++) {
cur *= X[i];
ma = max(ma, cur * Y[i] % mod);
}
return ma;
}
signed init(signed N, signed x[], signed y[]) {
::N = N;
for (int i = 0; i < N; i++) {
X.pb(x[i]);
Y.pb(y[i]);
seg.upd(i, N, log(X[i]), X[i]);
seg.upd(i, i, log(Y[i]), Y[i]);
}
return seg.query();
}
signed updateX(signed pos, signed val) {
seg.upd(pos, N, -log(X[pos]) + log(val), val * pot(X[pos], mod - 2) % mod);
X[pos] = val;
// seg.upd(pos, N, log(val), val);
return seg.query();
}
signed updateY(signed pos, signed val) {
seg.upd(pos, pos, -log(Y[pos]) + log(val), pot(Y[pos], mod - 2) * val % mod);
Y[pos] = val;
// seg.upd(pos, pos, log(val), val);
return seg.query();
}
