#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5e5 + 5;
const ll MOD = 1000000007LL;
vector<ll> x(N), y(N);
int n;
ll f(ll a, ll b){
return (a * b) % MOD;
}
struct lazyseg{
pair<long double, int> seg[4 * N];
long double lazy[4 * N];
lazyseg(){
for (int i = 0;i < 4 * N;i++){
lazy[i] = 0.0L;
seg[i] = {-INFINITY, 0};
}
}
void push(int nd, int l, int r){
seg[nd].first += lazy[nd];
if (l != r) {
lazy[nd * 2] += lazy[nd];
lazy[nd * 2 + 1] += lazy[nd];
}
lazy[nd] = 0.0L;
}
void builda(int nd, int l, int r, const vector<long double> &arr) {
if(l == r){
seg[nd] = {arr[l], -l};
return;
}
int md = (l + r) >> 1;
builda(nd * 2, l, md, arr);
builda(nd * 2 + 1, md + 1, r, arr);
seg[nd] = max(seg[nd * 2], seg[nd * 2 + 1]);
}
void upd(int nd, int l, int r, int ql, int qr, long double v){
push(nd, l, r);
if(r < ql || l > qr) return;
if(ql <= l && r <= qr){
lazy[nd] += v;
push(nd, l, r);
return;
}
int md = (l + r) >> 1;
upd(nd * 2, l, md, ql, qr, v);
upd(nd * 2 + 1, md + 1, r, ql, qr, v);
seg[nd] = max(seg[nd * 2], seg[nd * 2 + 1]);
}
int qry() { return -seg[1].second; }
} s;
struct segtree {
ll seg[4 * N];
void build(int nd, int l, int r) {
if (l == r) {
seg[nd] = x[l - 1] % MOD;
return;
}
int md = (l + r) >> 1;
build(nd * 2, l, md);
build(nd * 2 + 1, md + 1, r);
seg[nd] = f(seg[nd * 2], seg[nd * 2 + 1]);
}
void upd(int nd, int l, int r, int pos, int v){
if(l == r){
seg[nd] = (v % MOD + MOD) % MOD;
return;
}
int md = (l + r) >> 1;
if(pos <= md) upd(nd * 2, l, md, pos, v);
else upd(nd * 2 + 1, md + 1, r, pos, v);
seg[nd] = f(seg[nd * 2], seg[nd * 2 + 1]);
}
ll qry(int nd, int l, int r, int ql, int qr){
if(r < ql || l > qr) return 1;
if(ql <= l && r <= qr) return seg[nd];
int md = (l + r) >> 1;
return f(qry(nd * 2, l, md, ql, qr),qry(nd * 2 + 1, md + 1, r, ql, qr));
}
} pf;
int init(int NN, int X[], int Y[]) {
n = NN;
for(int i = 0;i < n;i++){
x[i] = X[i];
y[i] = Y[i];
}
vector<long double> arr(n + 1, -INFINITY);
long double pff = 0.0L;
for(int k = 1;k<=n;k++){
pff += logl(x[k - 1]);
arr[k] = pff + logl(y[k - 1]);
}
s.builda(1, 1, n, arr);
pf.build(1, 1, n);
int idx = s.qry();
ll prod = pf.qry(1, 1, n, 1, idx);
ll ans = f(prod, y[idx - 1] % MOD);
return (int)ans;
}
int updateX(int pos, int val) {
long double derm = logl(x[pos]);
long double nw = logl((long double)val);
long double dl = nw - derm;
s.upd(1, 1, n, pos + 1, n, dl);
x[pos] = val;
pf.upd(1, 1, n, pos + 1, val);
int idx = s.qry();
ll prod = pf.qry(1, 1, n, 1, idx);
ll ans = f(prod, y[idx - 1] % MOD);
return (int)ans;
}
int updateY(int pos, int val) {
long double derm = logl(y[pos]);
long double nw = logl((long double)val);
long double dl = nw - derm;
s.upd(1, 1, n, pos + 1, pos + 1, dl);
y[pos] = val;
int idx = s.qry();
ll prod = pf.qry(1, 1, n, 1, idx);
ll ans = f(prod, y[idx - 1] % MOD);
return (int)ans;
}
