#include <bits/stdc++.h>
using namespace std;
#ifndef wambule
#include "horses.h"
#else
#endif
const int mod = 1e9 + 7;
const int MXY = 1e9;
int MG(int a, int b) {
return 1ll * a * b % mod;
}
int G(int a, int b) {
if(a == -1 || b == -1) return -1;
if(1ll * a * b > MXY) return -1;
return a * b;
}
struct ovo {
ovo *l, *r;
int a, x, y, xm, ym;
ovo() {
l = r = NULL;
a = x = y = xm = ym = 1;
}
int AP() {
return MG(a, xm);
}
void P() {
if(l == NULL) l = new ovo();
if(r == NULL) r = new ovo();
int p = G(l->y, G(r->x, r->a));
if(p == -1 || p > l->a) {
a = r->a;
x = G(l->x, G(l->y, r->x));
y = r->y;
xm = MG(l->xm, MG(l->ym, r->xm));
ym = r->ym;
} else {
a = l->a;
x = l->x;
y = G(l->y, G(r->x, r->y));
xm = l->xm;
ym = MG(l->ym, MG(r->xm, r->ym));
}
}
void C(int vl, int rm) {
if(rm) a = y = ym = vl;
else x = xm = vl;
}
} *rt;
int globn;
void gng(int si, int vl, int rm, int l = 0, int r = globn - 1, ovo *&t = rt) {
if(t == NULL) t = new ovo();
int m = (l + r) / 2;
if(l == r) return t->C(vl, rm);
else if(m >= si) gng(si, vl, rm, l, m, t->l);
else gng(si, vl, rm, m + 1, r, t->r);
return t->P();
}
int updateX(int i, int x) {
gng(i, x, 0);
return rt->AP();
}
int updateY(int i, int y) {
gng(i, y, 1);
return rt->AP();
}
int init(int n, int x[], int y[]) {
rt = NULL, globn = n;
for(int i = 0; i < n; ++i) {
updateX(i, x[i]);
updateY(i, y[i]);
}
return rt->AP();
}
#ifdef wambule
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
return 0;
}
#endif
