#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<ll, ll> pll;
const ll LOG = 34;
const ll MOD = 1000000007;
const ll inf = 1e17;
#define db(x) cerr << #x << " = " << x << " | "
#define dbg(x) cerr << #x << " = " << x << "\n"
ll n, p;
vector<ll> x, y;
set<ll> s;
struct segtree {
vector<ll> t;
ll n;
segtree(vector<ll> x, ll N) {
n = N;
t.resize(2 * n);
for (ll i = 0; i < n; i++) t[i + n] = x[i];
for (ll i = n - 1; i > 0; i--) {
t[i] = max(t[i << 1], t[i << 1 | 1]);
}
}
void update(ll i, ll x) {
i += n;
t[i] = x;
for (i >>= 1; i > 0; i >>= 1) {
t[i] = max(t[i << 1], t[i << 1 | 1]);
}
}
ll query(ll l, ll r) {
ll lf = -inf, rf = -inf;
for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
if (l & 1) {
lf = max(lf, t[l++]);
}
if (!(r & 1)) {
rf = max(rf, t[r--]);
}
}
return max(lf, rf);
}
};
segtree tree({1}, 1);
ll binexp(ll b, ll e) {
ll r = 1;
while (e) {
if (e & 1) r = (r * b) % MOD;
b = (b * b) % MOD;
e >>= 1;
}
return r;
}
int updateX(int pos, int val);
int init(int N, int X[], int Y[]) {
n = N;
x.resize(n);
y.resize(n);
p = 1;
for (ll i = 0; i < n; i++) {
x[i] = X[i], y[i] = Y[i];
if (x[i] > 1 || i == 0) {
s.insert(i);
}
}
s.insert(0);
// s.insert(n);
tree = segtree(y, n);
ll cnt = 0;
for (auto it = s.begin(); it != s.end() && cnt < n - LOG; cnt++, ++it) {
p = (p * x[*it]) % MOD;
}
return updateX(0, x[0]);
}
bool mod(ll& x) {
if (x >= MOD) {
x %= MOD;
return 1;
}
return 0;
}
int updateX(int pos, int val) {
if (val == 1 && pos != 0) s.erase(pos);
else s.insert(pos);
auto it = --s.end();
ll cnt = 1;
ll old = -1;
while (cnt <= LOG) {
if (cnt == LOG) old = *it;
--it;
cnt++;
if (it == s.begin()) break;
}
if (cnt > LOG) {
if (old > -1) p = p * binexp(x[old], MOD - 2) % MOD;
p = p * val % MOD;
}
x[pos] = val;
ll res = 1;
bool up = 0;
cnt = 0;
for (auto it = --s.end(); ; --it) {
ll i = *it;
ll r;
if (it == --s.end()) r = n;
else r = *next(it);
ll cur_y = tree.query(i, r - 1);
if (up) {
res = res * x[i] % MOD;
} else {
res = x[i] * max(res, cur_y);
up |= mod(res);
}
++cnt;
if (cnt > LOG || it == s.begin()) break;
}
return (res * p) % MOD;
}
int updateY(int pos, int val) {
y[pos] = val;
tree.update(pos, val);
return updateX(0, x[0]);
}
