//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "horses.h"
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const ll INF = 1e9 + 7;
const int MAXN = 1e6 + 5;
ll pr[MAXN], x[MAXN], y[MAXN], tree[MAXN * 2], BIT[MAXN];
int n = 0;
ll qry(int ind) {
ll ret = 1;
ind++;
while (ind > 0) {
ret = (BIT[ind] * ret) % MOD;
ind -= ind & -ind;
}
return ret;
}
void upd(int ind, ll val) {
ind++;
while (ind <= n) {
BIT[ind] = (BIT[ind] * val) % MOD;
ind += ind & -ind;
}
}
ll pw(ll a, ll b) {
ll ret = 1;
while (b > 0) {
if (b & 1)
ret = (ret * a) % MOD, b--;
else
a = (a * a) % MOD, b /= 2ll;
}
return ret;
}
void build(int l, int r, int k) {
if (l == r) {
tree[k] = y[l];
return;
}
int m = (l + r) / 2;
build(l, m, k * 2);
build(m + 1, r, k * 2 + 1);
tree[k] = max(tree[k * 2], tree[k * 2 + 1]);
}
void upd(int l, int r, int k, int a, ll val) {
if (a < l || r < a)
return;
if (a <= l && r <= a) {
tree[k] = val;
return;
}
int m = (l + r) / 2;
upd(l, m, k * 2, a, val);
upd(m + 1, r, k * 2 + 1, a, val);
tree[k] = max(tree[k * 2], tree[k * 2 + 1]);
}
ll qry(int l, int r, int k, int a, int b) {
if (b < l || r < a)
return 0;
if (a <= l && r <= b)
return tree[k];
int m = (l + r) / 2;
return max(qry(l, m, k * 2, a, b), qry(m + 1, r, k * 2 + 1, a, b));
}
set<pii> rng;
ll getAns() {
auto it = rng.begin();
ll cur = 1, y = qry(0, n - 1, 1, it->fi, it->se);
ll prod = qry(n - 1);
ll ans = (prod * y) % MOD;
int cnt = 0;
while (cur < INF && it != rng.end()) {
cnt++;
ll ny = qry(0, n - 1, 1, it->fi, it->se);
if (cur * y < ny) {
ans = (prod * pw(qry(it->fi - 1), MOD - 2) % MOD) * ny % MOD;
cur = 1;
y = ny;
}
cur *= 1ll * (ll) x[it->fi];
it = next(it);
}
return ans;
}
int updateX(int pos, int val) {
pos = n-pos-1;
if (val == 1 && x[pos] != 1) {
auto it = rng.lower_bound({pos, -1});
pii nx = {pos, pos};
auto a = it, b = it;
pii flA = {-1, -1}, flB = {-1, -1};
if (it != rng.begin()) {
a = prev(a);
if (x[a->fi] == 1) {
nx.fi = a->fi;
flA = {a->fi, a->se};
}
}
if (it != (--rng.end())) {
b = next(b);
if (x[b->se] == 1) {
nx.se = b->se;
flB = {b->fi, b->se};
}
}
rng.erase(it);
if (flA.fi != -1)
rng.erase(flA);
if (flB.fi != -1)
rng.erase(flB);
rng.insert(nx);
} else if (x[pos] == 1 && val != 1) {
auto it = rng.lower_bound({pos, -1});
pii nx = {pos, pos};
if (it == rng.end() || it->fi > pos)
it = prev(it);
pii l = {it->fi, pos - 1};
pii r = {pos + 1, it->se};
rng.erase(it);
if (l.fi <= l.se)
rng.insert(l);
if (r.fi <= r.se)
rng.insert(r);
rng.insert(nx);
}
ll up = val;
up = (up * pw(x[pos], MOD - 2)) % MOD;
upd(pos, up);
x[pos] = val;
return (int) getAns();
}
int updateY(int pos, int val) {
pos = n-pos-1;
ll up = val;
up = (up * pw(y[pos], MOD - 2)) % MOD;
upd(0, n - 1, 1, pos, val);
y[pos] = val;
return (int) getAns();
}
int init(int n, int x[], int y[]) {
::n = n;
fill(BIT, BIT + n + 10, 1);
pr[n] = 1;
for (int i = 0; i < n; i++) {
pr[n-i-1] = (pr[n-i] * 1ll * (ll) x[n-i-1]) % MOD;
::y[n-i-1] = y[i];
::x[n-i-1] = x[i];
upd(n-i-1, x[i]);
}
for (int i = 0; i < n; i++) {
int j = i;
for (; j < n && ::x[j] == 1; j++);
if (j != i)
j--;
rng.insert({i, j});
i = j;
}
build(0, n - 1, 1);
return (int) getAns();
}
