#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
using ll=long long;
using ii=pair<int,int>;
const int mxN = 5e5+5;
const int mod = 1e9+7;
int N, X[mxN], Y[mxN];
struct node {
int s, e, m, px, my;
node *l, *r;
node(int s, int e): s(s), e(e), m((s+e)/2), px(0), my(0) {
if (s != e) {
l = new node(s,m);
r = new node(m+1,e);
}
}
void ux(int i, int v) {
if (s == e) { px = v; return; }
else if (i <= m) l->ux(i,v);
else r->ux(i,v);
px = 1LL * l->px * r->px % mod;
}
void uy(int i, int v) {
if (s == e) { my = v; return; }
else if (i <= m) l->uy(i,v);
else r->uy(i,v);
my = max(l->my,r->my);
}
int qx(int i, int j) {
if (s == i && e == j) return px;
if (j <= m) return l->qx(i,j);
if (i > m) return r->qx(i,j);
return 1LL * l->qx(i,m) * r->qx(m+1,j) % mod;
}
int qy(int i, int j) {
if (s == i && e == j) return my;
if (j <= m) return l->qy(i,j);
if (i > m) return r->qy(i,j);
return max(l->qy(i,m),r->qy(m+1,j));
}
ii qlxy(int i, int j) {
if (s == e) return ii(px>1?s:-1,my);
if (j <= m) return l->qlxy(i,j);
if (i > m) return r->qlxy(i,j);
if (qx(m+1,j) > 1) return r->qlxy(m+1,j);
ii a = qlxy(i,m);
a.second = max(a.second,r->qy(m+1,j));
return a;
}
} *root;
int calc() {
int j = N, gj = N, cy = 0;
ll px = 0;
FOR(i,1,31){
ii r = root->qlxy(0,j-1);
if (r.first == -1) break;
j = r.first;
if (r.second > 1LL*cy*px) {
gj = j;
cy = r.second;
px = X[r.first];
} else {
px *= X[r.first];
if (px > 1e9) break;
}
if (j == 0) break;
}
return 1LL * root->qx(0,gj) * cy % mod;
}
int init(int _N, int _X[], int _Y[]) {
N = _N;
root = new node(0,N-1);
FOR(i,0,N-1) {
X[i] = _X[i], Y[i] = _Y[i];
root->ux(i,X[i]);
root->uy(i,Y[i]);
}
return calc();
}
int updateX(int pos, int val) {
root->ux(pos,val);
return calc();
}
int updateY(int pos, int val) {
root->uy(pos,val);
return calc();
}
