#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5e5 + 5;
const ll MOD = 1e9 + 7;
vector<ll> x(N), y(N);
vector<ll> pf(N);
int n;
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;
}
}
void push(int nd, int l, int r){
if(lazy[nd] != 0){
seg[nd].first += lazy[nd];
if(l != r){
lazy[nd * 2] += lazy[nd];
lazy[nd * 2 + 1] += lazy[nd];
}
lazy[nd] = 0;
}
}
void build(int nd, int l, int r){
if(l == r){
seg[nd] = {-4e18, l};
return;
}
int md = (l + r) / 2;
build(nd * 2, l, md);
build(nd * 2 + 1, md + 1, r);
}
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) / 2;
upd(2 * nd, l, md, ql, qr, v);
upd(2 * nd + 1, md + 1, r, ql, qr, v);
seg[nd] = max(seg[nd * 2], seg[nd * 2 + 1]);
}
int qry(){
return seg[1].second;
}
}s;
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];
long double c = log(x[0]);
s.build(1, 1, n);
s.upd(1, 1, n, 1, 1, c);
pf[0] = x[0];
for(int i = 1;i<n;i++){
pf[i] = pf[i - 1] * x[i];
pf[i] %= MOD;
c += log(x[i]);
s.upd(1, 1, n, i + 1, i + 1, c + log(y[i]));
}
int idx = s.qry();
return (pf[idx - 1] * y[idx - 1]) % MOD;
}
int updateX(int pos, int val) {
s.upd(1, 1, n, pos + 1, n, -log(x[pos]));
x[pos] = val;
s.upd(1, 1, n, pos + 1, n, log(x[pos]));
int idx = s.qry();
return (pf[idx - 1] * y[idx - 1]) % MOD;
}
int updateY(int pos, int val) {
s.upd(1, 1, n, pos + 1, pos + 1, -log(y[pos]));
y[pos] = val;
s.upd(1, 1, n, pos + 1, pos + 1, log(y[pos]));
int idx = s.qry();
return (pf[idx - 1] * y[idx - 1]) % MOD;
}
