#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;
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){
if(fabsl(lazy[nd]) > 0.0L){
seg[nd].first += lazy[nd];
if(l != r){
lazy[nd * 2] += lazy[nd];
lazy[nd * 2 + 1] += lazy[nd];
}
lazy[nd] = 0.0L;
}
}
void build_from_array(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;
build_from_array(nd*2, l, md, arr);
build_from_array(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);
__int128 t = (__int128)seg[nd*2] * (__int128)seg[nd*2+1];
seg[nd] = (ll)(t % MOD);
}
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);
__int128 t = (__int128)seg[nd*2] * (__int128)seg[nd*2+1];
seg[nd] = (ll)(t % MOD);
}
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 ( (__int128)qry(nd*2, l, md, ql, qr) * (__int128)qry(nd*2+1, md+1, r, ql, qr)) % MOD;
}
} 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 pref = 0.0L;
for(int k = 1; k <= n; ++k){
pref += logl(x[k-1]);
arr[k] = pref + logl(y[k-1]);
}
s.build_from_array(1, 1, n, arr);
pf.build(1, 1, n);
int idx = s.qry();
ll prod = pf.qry(1, 1, n, 1, idx);
ll ans = ( (__int128)prod * (__int128)(y[idx - 1] % MOD) ) % 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;
if(fabsl(dl) > 0.0L){
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 = ( (__int128)prod * (__int128)(y[idx - 1] % MOD)) % 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;
if(fabsl(dl) > 0.0L){
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 = ((__int128)prod * (__int128)(y[idx - 1] % MOD)) % MOD;
return (int)ans;
}
