#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include "horses.h"
using namespace std;
using ll = long long;
struct node {
int L, M, R;
ll prod, mx;
};
int n;
ll MOD = 1e9 + 7;
vector <ll> x(5e5 + 1, 1);
vector <ll> y(5e5, 0);
vector <node> sgt(11e5);
vector <int> Lft(5e5 + 1, 0);
set <int> s;
void build_sgt(int a, int l, int r) {
sgt[a].L = l;
sgt[a].M = (l + r) / 2;
sgt[a].R = r;
if (r - l == 1) {
sgt[a].prod = x[l];
sgt[a].mx = y[l];
return;
}
build_sgt(2 * a, l, sgt[a].M);
build_sgt(2 * a + 1, sgt[a].M, r);
sgt[a].prod = (sgt[2 * a].prod * sgt[2 * a + 1].prod) % MOD;
sgt[a].mx = max(sgt[2 * a].mx, sgt[2 * a + 1].mx);
}
void update(int a, int i) {
if (sgt[a].R - sgt[a].L == 1) {
sgt[a].prod = x[i];
sgt[a].mx = y[i];
return;
}
if (i < sgt[a].M) update(2 * a, i);
else update(2 * a + 1, i);
sgt[a].prod = (sgt[2 * a].prod * sgt[2 * a + 1].prod) % MOD;
sgt[a].mx = max(sgt[2 * a].mx, sgt[2 * a + 1].mx);
}
ll query_prod(int a, int l, int r) {
if (r <= sgt[a].L || sgt[a].R <= l) return 1;
if (l <= sgt[a].L && sgt[a].R <= r) return sgt[a].prod;
return (query_prod(2 * a, l, r) * query_prod(2 * a + 1, l, r)) % MOD;
}
ll query_mx(int a, int l, int r) {
if (r <= sgt[a].L || sgt[a].R <= l) return 1;
if (l <= sgt[a].L && sgt[a].R <= r) return sgt[a].mx;
return max(query_mx(2 * a, l, r), query_mx(2 * a + 1, l, r));
}
ll get_ans() {
ll MX = 0, I = -1;
for (int i = n; i > 0; i = Lft[i]) {
MX *= x[i];
if (MX > MOD) break;
ll Y = query_mx(1, Lft[i], i);
if (Y > MX) { MX = Y; I = i; }
}
return (query_prod(1, 0, Lft[I] + 1) * query_mx(1, Lft[I], I)) % MOD;
}
int init(int N, int X[], int Y[]) {
n = N;
for (int i = 0; i < n; i++) { x[i] = X[i]; y[i] = Y[i]; }
build_sgt(1, 0, n);
for (int i = 1; i <= n; i++) {
Lft[i] = x[i - 1] == 1 ? Lft[i - 1] : i - 1;
if (x[i] > 1) s.insert(i);
}
s.insert(n);
return get_ans();
}
int updateX(int pos, int val) {
if (x[pos] == 1) {
int r = *s.upper_bound(pos);
Lft[pos] = Lft[r];
Lft[r] = pos;
s.insert(pos);
}
if (val == 1) {
int r = *s.upper_bound(pos);
Lft[r] = Lft[pos];
s.erase(pos);
}
x[pos] = val;
update(1, pos);
return get_ans();
}
int updateY(int pos, int val) {
y[pos] = val;
update(1, pos);
return get_ans();
}
