#include "horses.h"
#include "bits/stdc++.h"
#ifdef LOCAL
#include "grader.cpp"
#endif
using namespace std;
#define all(x) begin(x),end(x)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1;
const ll oo = 1e9;
const long long MD = 1e9+7;
template<long long MOD=MD> struct mdint {
int d=0;
mdint () {d=0;}
mdint (long long _d) : d(_d%MOD){};
friend mdint& operator+=(mdint& a, const mdint& o) {
a.d+=o.d; if(a.d>=MOD) a.d-=MOD;
return a;
}
friend mdint& operator-=(mdint& a, const mdint& o) {
a.d-=o.d; if(a.d<0) a.d+=MOD;
return a;
}
friend mdint& operator*=(mdint& a, const mdint& o) {
return a = mdint((ll)a.d*o.d);
}
mdint operator*(const mdint& o) const {
mdint res = *this;
res*=o;
return res;
}
mdint operator+(const mdint& o) const {
mdint res = *this;
res+=o;
return res;
}
mdint operator-(const mdint& o) const {
mdint res = *this;
res-=o;
return res;
}
mdint operator^(long long b) const {
mdint tmp = 1;
mdint power = *this;
while(b) {
if(b&1) {
tmp = tmp*power;
}
power = power*power;
b/=2;
}
return tmp;
}
friend mdint operator/=(mdint& a, const mdint& o) {
a *= (o^(MOD-2));
return a;
}
mdint operator/(const mdint& o) {
mdint res = *this;
res/=o;
return res;
}
bool operator==(const mdint& o) { return d==o.d;}
bool operator!=(const mdint& o) { return d!=o.d;}
friend istream& operator>>(istream& c, mdint& a) {return c >> a.d;}
friend ostream& operator<<(ostream& c, const mdint& a) {return c << a.d;}
};
using mint = mdint<MD>;
struct node {
mint prod=1;
__int128 mx=1;
int prodl=1;
node() {
}
node(int x, int y) {
mx = (ll)x*y;
prod=x;
prodl=x;
}
void merge(const node& o) {
prod*=o.prod;
mx = max(mx,o.mx*prodl);
if((ll)prodl*o.prodl>oo) prodl = oo;
else prodl*=o.prodl;
}
friend node merge(node a, const node& b) {
a.merge(b);
return a;
}
};
struct segtree {
int ptwo,n;
vector<node> seg;
segtree(){}
node& operator[](int i) {
return seg[i+ptwo];
}
segtree(int nn) {
ptwo=1<<__lg(2*nn-1);
n=nn;
seg.assign(ptwo*2,node(1,0));
}
auto query(int l, int r) {
assert(l>=0 and l<ptwo and r >=0 and r<ptwo);
l+=ptwo; r+=ptwo;
node resl, resr;
while(l and l<=r) {
if(l%2==1) resl = merge(resl,seg[l++]);
if(r%2==0) resr = merge(seg[r--],resr);
l/=2; r/=2;
}
return merge(resl,resr);
}
auto cutoff() {
if(seg[1].prodl<oo) return 0;
int i=1;
node nd = {};
while(i<ptwo) {
if(merge(nd,seg[i*2+1]).prodl>=oo) {
i=i*2+1;
} else {
i=i*2;
nd.merge(seg[i*2+1]);
}
}
return i-ptwo;
}
void update(int i, int x, int y) {
assert(i>=0 and i<ptwo);
i+=ptwo;
seg[i] = node(x,y);
for(i/=2;i>=1;i/=2) {
seg[i] = merge(seg[2*i],seg[2*i+1]);
}
}
mint best() {
auto i = cutoff();
if(i==0) {
return ll(query(0,n-1).mx % MD);
}
return query(0,i-1).prod * ll( query(i,n-1).mx % MD);
}
void build() {
for(int i=ptwo-1;i>=1;--i) {
seg[i] = merge(seg[2*i],seg[2*i+1]);
}
}
};
segtree seg;
int *x, *y;
int init(int N, int X[], int Y[]) {
x=X,y=Y;
seg = segtree(N);
for(auto i=0;i<N;++i) {
seg[i] = node(X[i],Y[i]);
}
seg.build();
return seg.best().d;
}
int updateX(int pos, int val) {
x[pos]=val;
seg.update(pos,x[pos],y[pos]);
return seg.best().d;
}
int updateY(int pos, int val) {
y[pos] = val;
seg.update(pos,x[pos],y[pos]);
return seg.best().d;
}
