#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
#define ll long long
ll n, x[1500000], y[1500000], mod = 10e9 + 7;
struct SegmentTree {
vector<ll> mul;
vector<pair<ll, ll>> mx;
void init() {
mx.resize(n * 3);
mul.resize(n * 3, 1);
}
void build(int k, int l, int r) {
if (l == r) {
mx[k] = { y[l], l };
mul[k] = x[l];
return;
}
build(k * 2, l, (l + r) / 2);
build(k * 2 + 1, (l + r) / 2 + 1, r);
mx[k] = max(mx[k * 2], mx[k * 2 + 1]);
mul[k] = mul[k * 2] * mul[k * 2 + 1];
mul[k] %= mod;
}
void update(int k, int l, int r, int i, ll v, bool t) {
if (l > i || r < i) return;
if (l == r) {
if (!t) mx[k].first = v;
else mul[k] = v;
return;
}
update(k * 2, l, (l + r) / 2, i, v, t);
update(k * 2 + 1, (l + r) / 2 + 1, r, i, v, t);
mx[k] = max(mx[k * 2], mx[k * 2 + 1]);
mul[k] = mul[k * 2] * mul[k * 2 + 1];
mul[k] %= mod;
}
ll getX(int k, int l, int r, int i, int j) {
if (l > j || r < i) return 1;
if (i <= l && r <= j) return mul[k];
return getX(k * 2, l, (l + r) / 2, i, j) * getX(k * 2 + 1, (l + r) / 2 + 1, r, i, j);
}
pair<ll, ll> getY(int k, int l, int r, int i, int j) {
if (l > j || r < i) return {0, 0};
if (i <= l && r <= j) return mx[k];
return max( getY(k * 2, l, (l + r) / 2, i, j), getY(k * 2 + 1, (l + r) / 2 + 1, r, i, j) );
}
} sgt;
set<int> s;
ll solve() {
auto itf = --s.end(), its = --s.end();
itf--;
ll val = -1, id = n;
for (int i = 0; i < 32 && its != s.begin(); i++) {
pair<ll, ll> t = sgt.getY(1, 0, n - 1, *itf, *its - 1);
if (t.first > val) {
val = t.first;
id = t.second;
}
val *= x[*itf];
if (val > 2e9 || itf == s.begin()) break;
itf--;
its--;
}
return 1LL * sgt.getX(1, 0, n - 1, 0, id) * y[id] % 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];
if (x[i] != 1) s.insert(i);
}
s.insert(0);
s.insert(n);
sgt.init();
sgt.build(1, 0, n - 1);
return solve();
}
int updateX(int pos, int val) {
if (x[pos] != 1 && pos != 0) s.erase(pos);
x[pos] = val;
sgt.update(1, 0, n - 1, pos, val, 1);
if (val != 1) s.insert(pos);
return solve();
}
int updateY(int pos, int val) {
y[pos] = val;
sgt.update(1, 0, n - 1, pos, val, 0);
return solve();
}
