// In the name of Allah
#include <bits/stdc++.h>
#include "horses.h"
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 {
ll mul, mx; int 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;
node f(node a, node b) {
node res;
res.mul = a.mul * b.mul % mod;
res.mx = max(a.mx, b.mx);
res.ind = max(a.ind, b.ind);
return res;
}
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]);
}
node 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 ca;
if (l == tl && r == tr) return t[v];
int mid = (tl + tr) / 2;
return f(get_res(2 * v + 1, tl, mid, l, r), get_res(2 * v + 2, mid, tr, l, r));
}
ll get_ans() {
ll mx = 1; int j = n;
while (j > 0) {
node res = get_res(0, 0, n, 0, j);
int k = res.ind;
if (k == -1) {
mx = max(mx, res.mx); j = 0;
}
else {
res = get_res(0, 0, n, k, j);
mx = max(mx, res.mx) * A[k].F; j = k;
if (mx >= mod) break;
}
}
return (mx % mod) * get_res(0, 0, n, 0, j).mul % 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);
return get_ans();
}
int updateX(int i, int val) {
A[i].F = val;
upd(0, 0, n, i);
return get_ans();
}
int updateY(int i, int val) {
A[i].S = val;
upd(0, 0, n, i);
return get_ans();
}
