#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#include "horses.h"
const int MOD = 1e9+7;
template<class T> struct SegmentTree{
function<T(T, T)> comb = [](T u, T v){ return ((u % MOD) * (v % MOD)) % MOD; };
T ID = 1; int n = 1, i; vector<T> a;
void init(int N){ while((n+=n) < N); a.assign(2*n, ID); }
SegmentTree& operator[](int j){ i=j+n; return *this; }
void operator=(T v){
for(a[i]=v; i/=2; ) a[i] = comb(a[2*i], a[2*i+1]); }
T operator()(int l, int r){
T lx = ID, rx = ID;
for(l+=n, r+=n+1; l<r; l/=2, r/=2){
if(l & 1) lx = comb(lx, a[l++]);
if(r & 1) rx = comb(a[--r], rx);
}
return comb(lx, rx);
}
};
int n;
SegmentTree<ll> x;
SegmentTree<int> y;
set<int> s;
int find(){
vector<array<int, 2>> a;
int cnt = 0, j = n;
s.insert(0);
for(int i : s){
if(++cnt > 32) break;
a.push_back({-i, y(-i, j-1)});
j = -i;
}
reverse(a.begin(), a.end());
array<ll, 3> c = {1, 0, 0};
for(auto &i : a){
c[0] *= x(i[0], i[0]);
if(c[0] * i[1] > c[2]){
c[2] = c[0] * i[1];
c[1] = ((x(0, i[0]) % MOD) * i[1]) % MOD;
}
}
return c[1];
}
int init(int N, int X[], int Y[]){
x.init(n=N); y.init(n);
y.ID = -1; y.comb = [](int u, int v){ return max(u, v); };
for(int i=0; i<n; ++i){
y[i] = Y[i]; x[i] = X[i];
if(X[i] > 1) s.insert(-i);
}
return find();
}
int updateX(int i, int v){
auto f = s.find(-i);
if(v < 2 && f != s.end()) s.erase(f);
if(v > 1) s.insert(-i);
x[i] = v;
return find();
}
int updateY(int i, int v){
y[i] = v;
return find();
}
