#include "bits/stdc++.h"
#include "horses.h"
using namespace std;
#define ll long long
#define all(x) x.begin(),x.end()
#define sz(x) (ll)x.size()
const ll N = 5e5 + 5;
const ll INF = 1e18 + 5;
const ll MOD = 1e9 + 7;
inline ll add(ll a,ll b){
if(a+b>=MOD) return a+b-MOD;
return a+b;
}
inline ll mult(ll a,ll b){
if(a*b>=MOD) return a*b%MOD;
return a*b;
}
inline ll fast(ll a,ll b,ll res=1){
for(;b;a=mult(a,a),b>>=1) if(b&1) res=mult(res,a);
return res;
}
inline ll inv(ll a){
return fast(a,MOD-2);
}
struct SegT{
vector<ll> seg;
ll n,def;
SegT(ll _n,ll _def){
n=_n,def=_def;
seg.assign(4*n+5,def);
}
void upd(ll rt,ll l,ll r,ll ind,ll u){
if(r<ind || l>ind) return;
if(l==r){
seg[rt]=u;
return;
}
ll mid=(l+r)/2;
upd(rt*2,l,mid,ind,u),upd(rt*2+1,mid+1,r,ind,u);
seg[rt]=max(seg[rt*2],seg[rt*2+1]);
}
ll query(ll rt,ll l,ll r,ll gl,ll gr){
if(r<gl || l>gr) return def;
if(l>=gl && r<=gr) return seg[rt];
ll mid=(l+r)/2;
return max(query(rt*2,l,mid,gl,gr),query(rt*2+1,mid+1,r,gl,gr));
}
};
ll fw[N],n;
set<ll> s;
SegT T(N,-INF);
array<ll,2> ar[N];
inline void upd(ll c,ll u){
for(;c<N;c+=c&-c) fw[c]=mult(fw[c],u);
}
inline ll query(ll c,ll res=1){
for(;c;c-=c&-c) res=mult(res,fw[c]);
return res;
}
inline ll find_ans(){
vector<ll> v;
set<ll>::reverse_iterator it = s.rbegin();
ll ekle = 35;
while(ekle--){
v.push_back(*it);
it++;
if(it==s.rend()) break;
}
reverse(all(v));
ll m = sz(v);
vector<ll> g;
for(ll i = 0; i < m; i++) g.push_back(T.query(1,1,n,v[i],(i+1==m ? n+1 : v[i+1])-1));
ll best = 0 , as = 1;
for(ll i = 1 ; i < m ;i++){
ll ind = v[i];
as *= ar[ind][0];
if(as >= (g[best]+g[i]-1)/g[i]){
best = i;
as = 1;
}
}
return mult(g[best],query(v[best]));
}
int init(int nn, int X[], int Y[]){
n = nn;
for(ll i = 1; i <= n ; i++) ar[i][0] = X[i-1], ar[i][1] = Y[i-1];
fill(fw,fw+N,1);
for(ll i = 1 ; i <= n ; i++) upd(i,ar[i][0]);
for(ll i=1;i<=n;i++) if(ar[i][0] >= 2) s.insert(i);
for(ll i=1;i<=n;i++) T.upd(1,1,n,i,ar[i][1]);
return (int)find_ans();
}
int updateX(int pos, int val){
return 0;
}
int updateY(int pos, int val){
return 0;
}
/*void _(){
cin >> n;
for(ll i = 1; i <= n ; i++) cin >> ar[i][0] >> ar[i][1];
fill(fw,fw+N,1);
for(ll i = 1 ; i <= n ; i++) upd(i,ar[i][0]);
for(ll i=1;i<=n;i++) if(ar[i][0] >= 2) s.insert(i);
for(ll i=1;i<=n;i++) T.upd(1,1,n,i,ar[i][1]);
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
ll tc=1;//cin >> tc;
while(tc--) _();
}*/
