// compile with -O2 -std=gnu++17
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const ll mod = 1000000007LL;
const long double THRESH = 1e9L; // threshold used in original code
// fast powmod
ll modpow(ll a, ll e) {
ll r = 1 % mod;
a %= mod;
while (e) {
if (e & 1) r = (r * a) % mod;
a = (a * a) % mod;
e >>= 1;
}
return r;
}
ll invmod(ll a){ return modpow((a%mod+mod)%mod, mod-2); }
// Fenwick (BIT) for multiplicative prefix product modulo `mod`.
struct Fenwick {
int n;
vector<ll> bit;
Fenwick() : n(0) {}
Fenwick(int _n){ init(_n); }
void init(int _n){
n = _n;
bit.assign(n+1, 1);
}
// multiply index i by val (mod)
void mul_point(int i, ll val){
while(i <= n){
bit[i] = (bit[i] * val) % mod;
i += i & -i;
}
}
// prefix product 1..i
ll prefix(int i) const {
ll res = 1;
while(i > 0){
res = (res * bit[i]) % mod;
i -= i & -i;
}
return res;
}
// range product l..r
ll range(int l,int r) const {
if(l>r) return 1;
ll a = prefix(r);
ll b = prefix(l-1);
return (a * invmod(b)) % mod;
}
};
// iterative segment tree for range max, point update
struct SegMax {
int n;
int size;
vector<int> seg;
SegMax(){}
void init(int _n){
n = _n;
size = 1;
while(size < n) size <<= 1;
seg.assign(2*size, 0);
}
void set_point(int pos, int val){ // pos in [1..n]
int i = pos - 1 + size;
seg[i] = val;
for(i >>= 1; i; i >>= 1)
seg[i] = max(seg[2*i], seg[2*i+1]);
}
int range_max(int l,int r){ // inclusive, 1..n
if(l>r) return 0;
int L = l - 1 + size, R = r - 1 + size;
int ans = 0;
while(L <= R){
if(L & 1) ans = max(ans, seg[L++]);
if(!(R & 1)) ans = max(ans, seg[R--]);
L >>= 1; R >>= 1;
}
return ans;
}
};
static int N_global = 0;
static vector<int> Xarr, Yarr; // 0..N
static Fenwick fen;
static SegMax segy;
static set<int> special; // indices i where X[i] > 1, plus sentinel 0
static const ll SENTINEL_X0 = 1000000000LL; // same as 1e9 from your code
// get segment end for special index s: next(s) - 1, or N_global if none
inline int seg_end_of(int s){
auto it = special.upper_bound(s);
if(it == special.end()) return N_global;
return (*it) - 1;
}
// compute answer following the same logic as original code
int compute_answer(){
// collect suffix of special indices starting from largest until product >= 1e9
deque<pair<int,int>> a; // (startIndex, endIndex)
__int128 tem = 1;
for(auto it = special.rbegin(); it != special.rend(); ++it){
int s = *it;
int r = seg_end_of(s);
a.emplace_front(s, r);
tem *= (__int128) Xarr[s];
if(tem >= (__int128)1000000000LL) break;
}
// special-case matching original:
// if the first picked segment starts at 0 (sentinel), temporarily remove it from consideration
long long ans1 = 0;
__int128 intem = tem;
if(!a.empty() && a.front().first == 0){
// divide out sentinel contribution
tem /= (__int128)Xarr[0]; // Xarr[0] = 1e9 sentinel
intem /= (__int128)Xarr[0];
if(tem < (__int128)1000000000LL){
// ans1 = ry.mx(1,n) in your code
ans1 = segy.range_max(1, N_global);
}
// remove sentinel from deque (original code popped it)
a.pop_front();
}
if(a.empty()){
// nothing chosen: return overall max y
return segy.range_max(1, N_global) % (int)mod;
}
// compute ma = max over selected segments of (product_of_selected_specials_prefix * maxY_in_segment)
__int128 prodprefix = 1;
__int128 ma128 = 0;
for(auto &pr : a){
int s = pr.first, r = pr.second;
prodprefix *= (__int128) Xarr[s];
int localMaxY = 0;
if(s == 0){
// should not happen here (we popped sentinel); but safe fallback
localMaxY = segy.range_max(1, N_global);
} else {
localMaxY = segy.range_max(s, r);
}
__int128 candidate = prodprefix * (__int128)localMaxY;
if(candidate > ma128) ma128 = candidate;
}
// multiply by product of x's on left of first selected special: rx.mul(1, a[0].fi-1)
int firstSpecial = a.front().first;
ll leftProdMod = fen.range(1, max(0, firstSpecial - 1));
// incorporate ans1 if applicable (original logic took max with ma after mod)
ll ma_mod = (ll)( ( (long long)(ma128 % (__int128)mod) ) % mod );
if(intem < (__int128)1000000000LL){
ma_mod = max(ma_mod, (ll)ans1); // ans1 already fits in int
}
ll result = (ma_mod * leftProdMod) % mod;
return (int) result;
}
// API functions (match original names/behaviour)
int init(int N, int X[], int Y[]){
N_global = N;
Xarr.assign(N+1, 1);
Yarr.assign(N+1, 0);
// index 0 sentinel
Xarr[0] = (int)SENTINEL_X0;
// Fenwick only stores indices 1..N
fen.init(N);
segy.init(N);
special.clear();
special.insert(0); // sentinel
// fill arrays and structures
for(int i=1;i<=N;i++){
Xarr[i] = X[i-1];
Yarr[i] = Y[i-1];
// fenwick multiply by X[i]
fen.mul_point(i, (Xarr[i] % mod + mod) % mod);
// segtree for Y
segy.set_point(i, Yarr[i]);
if(Xarr[i] > 1) special.insert(i);
}
// answer
return compute_answer();
}
int updateX(int idx0, int v){ // idx0 is 0-based
int i = idx0 + 1;
int old = Xarr[i];
if(old == v) return compute_answer();
// update fenwick: multiply index i by (v * inv(old))
ll mulval = ( (v % mod + mod) % mod ) * invmod( (old % mod + mod) % mod ) % mod;
fen.mul_point(i, mulval);
Xarr[i] = v;
// maintain special set
bool wasSpecial = (old > 1);
bool nowSpecial = (v > 1);
if(wasSpecial && !nowSpecial){
special.erase(i);
} else if(!wasSpecial && nowSpecial){
special.insert(i);
}
return compute_answer();
}
int updateY(int idx0, int v){
int i = idx0 + 1;
Yarr[i] = v;
segy.set_point(i, v);
return compute_answer();
}
