#include "horses.h"
#include<bits/stdc++.h>
#include<bits/extc++.h>
#pragma GCC optimize(2)
using namespace std;
using namespace __gnu_pbds;
#define LB lower_bound
#define UB upper_bound
#define P(x) pair<x,x>
#define TP(x) tuple<x,x,x>
#define V vector
#define F first
#define S second
#define TT get<2>
#define TS get<1>
#define TF get<0>
#define LE less_equal
#define GE greater_equal
#define GR greater
#define all(x) x.begin(), x.end()
#define For(i,s,n) for(int i = s; i < n; i++)
#define Forit(i,s,e) for(auto i = s; i != e; i++)
#define Rfor(i, n) for(int i = n; i>-1; i--)
#define int long long // might cause errors if problem is ioi style
#define ll long long // replacement for above if problem is ioi style
#define PB push_back
#define bll __int128_t //warning: not possible to IO a bll
#define ubll __uint128_t // IO doesn't work for ubll too
#define US unsigned
#define rbt tb_tree_tag
#define splt splay_tree_tag
#define avlt ov_tree_tag
#define ForR(i,v) for(auto i:v)
#define Tree(t, cp, tg) tree<t, null_type, cp<i>, tg, tree_order_statistics_node_update>
#define PQ priority_queue
#define mod ((int)(1e9+7))
#define rch(x) x = getchar_unlocked()
#define inf ((int)(1e18))
#define db double
#define ldb long double
#define MXN 500100 //change this value according to problem
#define MXM 200100 //change this too
int n, x[MXN], total = 1;
struct node {
int l=0, r=0, v=v;
} seg[MXN*4];
set<int> st;
void build(int i = 1, int l = 0, int r = MXN) {
seg[i] = {l,r,0};
if(l-r) build(i*2, l, l+r>>1), build(i*2+1, l+r+2>>1, r);
}
void update(int x, int v, int i = 1){
if (seg[i].l > x || x > seg[i].r) return;
if (seg[i].l == seg[i].r){
seg[i].v = v;
return;
}
int tm = (seg[i].l + seg[i].r) / 2;
update(x, v, i * 2); update(x, v, i * 2 + 1);
seg[i].v = max(seg[i * 2].v, seg[i * 2 + 1].v);
}
int query(int l, int r, int i = 1){
if (l > seg[i].r || seg[i].l > r) return 0;
if (l <= seg[i].l && seg[i].r <= r) return seg[i].v;
int tm = (seg[i].l + seg[i].r) / 2;
return max(query(l, r, i * 2), query(l, r, i * 2 + 1));
}
int inv(int x){
int k = mod - 2, res = 1;
while (k){
if (k % 2) res = res * x % mod;
x = x * x % mod;
k >>= 1;
}
return res;
}
int solve(){
int res = 1, horses = 1;
int start = 0;
Forit (it,st.rbegin(),st.rend()){
if (horses * x[*it] > mod) break;
start = *it; horses *= x[*it];
}
int last = 0;
if (start) last = *(--st.LB(start));
res = query(last, n);
horses = 1;
Forit (it, st.LB(start),st.end()){
int i = *it;
horses *= x[i];
int best_y = query(i, n);
res = max(res, best_y * horses);
}
return res%mod*total%mod*inv(horses)%mod;
}
signed init(signed N, signed X[], signed Y[]){
build();
n = N;
x[0] = 1;
st.insert(0);
For (i,1,N+1){
x[i] = X[i - 1]; update(i, Y[i - 1]);
if (x[i] == 1) continue;
total = (total * x[i]) % mod;
st.insert(i);
}
return solve();
}
signed updateX(signed pos, signed val){
pos++;
if (x[pos]-1){
total = (total * inv(x[pos])) % mod;
st.erase(pos);
}
x[pos] = val;
if (x[pos]-1){
total = (total * x[pos]) % mod;
st.insert(pos);
}
return solve();
}
signed updateY(signed pos, signed val){
update(pos+1, val);
return solve();
}
