// In the name of Allah
#include <bits/stdc++.h>
#include "horses.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct node {
int mul, mx, ind;
};
const int maxn = (1 << 19) + 4;
const int maxlg = 20;
const int mod = 1e9 + 7;
int n; pll A[maxn];
node t[2 * maxn], ca;
int R; ll valx, lst;
node f(node a, node b) {
node res;
res.mul = 1ll * a.mul * b.mul % mod;
res.mx = max(a.mx, b.mx);
res.ind = max(a.ind, b.ind);
return res;
}
pii fx(pii a, pii b) {
return Mp(max(a.F, b.F), max(a.S, b.S));
}
void build(int v, int tl, int tr) {
if (tr - tl == 1) {
t[v].mul = A[tl].F; t[v].mx = A[tl].S;
if (A[tl].F == 1) t[v].ind = -1;
else t[v].ind = tl;
return ;
}
int mid = (tl + tr) / 2;
build(2 * v + 1, tl, mid); build(2 * v + 2, mid, tr);
t[v] = f(t[2 * v + 1], t[2 * v + 2]);
}
void upd(int v, int tl, int tr, int i) {
if (i >= tr || i < tl) return ;
if (tr - tl == 1) {
t[v].mul = A[tl].F; t[v].mx = A[tl].S;
if (A[tl].F == 1) t[v].ind = -1;
else t[v].ind = tl;
return ;
}
int mid = (tl + tr) / 2;
upd(2 * v + 1, tl, mid, i); upd(2 * v + 2, mid, tr, i);
t[v] = f(t[2 * v + 1], t[2 * v + 2]);
}
pll get_res(int v, int tl, int tr, int l, int r) {
l = max(l, tl); r = min(r, tr);
if (l >= tr || r <= tl) return Mp(ca.mx, ca.ind);
if (l == tl && r == tr) return Mp(t[v].mx, t[v].ind);
int mid = (tl + tr) / 2;
return fx(get_res(2 * v + 1, tl, mid, l, r), get_res(2 * v + 2, mid, tr, l, r));
}
int get_mul(int v, int tl, int tr, int r) {
r = min(r, tr);
if (r <= tl) return ca.mul;
if (r == tr) return t[v].mul;
int mid = (tl + tr) / 2;
if (r <= mid) return get_mul(2 * v + 1, tl, mid, r);
else return 1ll * t[2 * v + 1].mul * get_mul(2 * v + 2, mid, tr, r) % mod;
}
ll get_ans(int ind) {
if (ind >= R) {
ll mx = 1; int j = n;
while (j > 0) {
pll res = get_res(0, 0, n, 0, j);
int k = res.S;
if (k == -1) {
mx = max(mx, res.F); j = 0;
}
else {
res = get_res(0, 0, n, k, j);
mx = max(mx, (ll) res.F) * A[k].F; j = k;
if (mx >= 1e9) break;
}
}
R = j; valx = mx % mod;
}
return valx * get_mul(0, 0, n, R) % mod;
}
int init(int N, int X[], int Y[]) {
n = N;
for (int i = 0; i < n; i++) A[i] = Mp(X[i], Y[i]);
ca.mul = 1; ca.mx = 0; ca.ind = -1;
build(0, 0, n); R = -1;
return lst = get_ans(n);
}
int updateX(int i, int val) {
if (A[i].F == val) return lst;
A[i].F = val;
upd(0, 0, n, i);
return lst = get_ans(i);
}
int updateY(int i, int val) {
if (A[i].S == val) return lst;
A[i].S = val;
upd(0, 0, n, i);
return lst = get_ans(i);
}
