#include "horses.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
const int MAXN = (int) 5e5 + 5;
const int mod = (int) 1e9+7;
typedef long long ll;
typedef pair<ll, ll> pll;
ll x[MAXN], y[MAXN], pre[MAXN], n;
set<pll> st;
ll bp(ll a, ll b){
ll res = 1;
while(b){
if(b % 2) res = (res * a) % mod;
a = (a * a) % mod;
b = b / 2;
}
return res;
}
ll t[4*MAXN];
void build(int v, int l, int r){
if(l == r){ t[v] = y[l];}
else{
int m = (l + r) / 2;
build(2*v, l, m);
build(2*v + 1, m + 1, r);
t[v] = max(t[2*v], t[2*v + 1]);
}
}
void upd(int v, int tl, int tr, int pos){
if(tl == tr){
t[v] = y[tl];
}else{
int tm = (tl + tr) / 2;
if(pos <= tm)
upd(2*v, tl, tm, pos);
else
upd(2*v + 1, tm + 1, tr, pos);
t[v] = max(t[2*v], t[2*v + 1]);
}
}
ll que(int v, int tl , int tr, int l, int r){
if(l > r) return 0;
else if(tl == l && tr == r)
return t[v];
else{
int tm = (tl + tr) / 2;
return max(que(2*v, tl, tm, l, min(tm, r)), que(2*v + 1, tm + 1, tr, max(tm + 1, l), r));
}
}
ll ft[MAXN];
void updi(int v, int val){
for(; v < MAXN; v += (v&-v)){
ft[v] = (ft[v] * val) % mod;
}
}
ll get(int v){
ll res = 1;
for(; v; v -= (v&-v)){
res = (res * ft[v]) % mod;
}
return res;
}
ll gt(){
ll top = 1;
ll mx = 0;
auto u = st.end();
do{
u--;
top *= (*u).ss;
} while(u != st.begin() && top < mod);
if(top >= mod) u++;
top = 1;
auto v = u;
//cerr<<(*u).ff<<" "<<(*u).ss.ff<<endl;
for(; u != st.end(); u++){
if(u != v)
top *= (*u).ss;
int l = (*u).ff;
int r = (next(u) == st.end() ? n : (*next(u)).ff - 1);
mx = max(mx, top*que(1, 0, n, l, r));
//cerr<<l<<" "<<r<<" "<<mx<<endl;
}
mx %= mod;
return get((*v).ff) * mx % mod;
}
int init(int N, int X[], int Y[]) {
n = N;
for(int i = 0; i <= n; i++) ft[i] = 1;
for(int i = 1; i <= n; i++){
x[i] = X[i - 1];
y[i] = Y[i - 1];
if(x[i] == 1){
if(!st.empty() && (*st.begin()).ss == 1){
}else{
st.insert({i, x[i]});
}
}else{
st.insert({i, x[i]});
}
updi(i, x[i]);
}
for(int i = 1; i <= n; i++){
pre[i] = pre[i - 1] * x[i] % mod;
}
build(1, 0, n);
return gt();
}
int updateX(int pos, int val) {
pos++;
updi(pos, bp(x[pos], mod - 2)*val % mod);
if(x[pos] == val){
}else if(x[pos] == 1){
x[pos] = val;
auto u = prev(st.upper_bound({pos, mod}));
int l = (*u).ff;
int r;
if(next(u) == st.end()){
r = n;
}else{
r = (*next(u)).ff - 1;
}
st.erase(u);
if(l != pos)
st.insert({l, 1});
if(r != pos)
st.insert(make_pair(pos + 1, 1));
st.insert({pos, val});
}else{
if(val == 1){
auto u = st.lower_bound({pos, x[pos]});
st.erase(u);
x[pos] = val;
auto v = st.insert({pos, 1}).ff;
if(v != st.end()){
u = v;
u++;
if((*u).ss == 1){
st.erase(u);
}
}
if(v != st.begin()){
u = v;
u--;
if((*u).ss == 1){
st.erase(v);
}
}
}else{
auto u = st.lower_bound({pos, x[pos]});
st.erase(u);
x[pos] = val;
st.insert({pos, x[pos]});
}
}
return gt();
}
int updateY(int pos, int val) {
pos++;
y[pos] = val;
upd(1, 0, n, pos);
return gt();
}
