#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
#define pb push_back
#define ll long long
const ll MOD=1e9+7,MAXN=5e5+5;
vector<int> x,y;
multiset<int> p;
pair<int,int> seg[MAXN*4];
ll offset=1,seg2[MAXN*4];
void update(int idx,int val){
idx+=offset;
seg[idx]={val,idx-offset};
idx/=2;
while(idx>0){
seg[idx]=max(seg[idx*2],seg[idx*2+1]);
idx/=2;
}
}
void update2(int idx,int val){
idx+=offset;
seg2[idx]=val;
idx/=2;
while(idx>0){
seg2[idx]=seg2[idx*2]*seg2[idx*2+1]%MOD;
idx/=2;
}
}
pair<int,int> query(int node,int qlo,int qhi,int lo,int hi){
if(lo>=qlo && hi<=qhi)return seg[node];
if(lo>qhi || hi<qlo)return {-1,-1};
int mid=(lo+hi)/2;
return max(query(node*2,qlo,qhi,lo,mid),query(node*2+1,qlo,qhi,mid+1,hi));
}
ll query2(int node,int qlo,int qhi,int lo,int hi){
if(lo>=qlo && hi<=qhi)return seg2[node];
if(lo>qhi || hi<qlo)return 1;
int mid=(lo+hi)/2;
return query2(node*2,qlo,qhi,lo,mid)*query2(node*2+1,qlo,qhi,mid+1,hi)%MOD;
}
ll pref[65];
bool cmp(pair<int,int> p1,pair<int,int> p2){
if(p1.first>p2.first)swap(p1,p2);
if(pref[p2.first]/pref[p1.first]>y[p1.first])return 1;
ll mult=pref[p2.first]/pref[p1.first]*y[p2.first];
return mult>y[p1.first];
}
ll sol(){
ll last=y.size()-1;
auto it=p.end();
vector<pair<ll,ll>> vec;
ll mult=1;
for(int i=0;i<min(31,(int)p.size());i++){
it--;
int id=*it;
if(last>id)vec.pb(query(1,id+1,last,0,offset-1));
vec.pb({y[id],id});
mult*=x[id];
if(mult>=(long long)1e9){
last=-1;
break;
}
last=id-1;
}
if(p.size()<31 && last>=0)vec.pb(query(1,0,last,0,offset-1));
for(int i=0;i<vec.size();i++)swap(vec[i].first,vec[i].second);
sort(vec.begin(),vec.end());
pref[0]=x[vec[0].first];
for(int i=1;i<vec.size();i++)pref[i]=x[vec[i].first]*pref[i-1];
sort(vec.begin(),vec.end(),cmp);
ll ans=query2(1,0,vec[0].first,0,offset-1);
ans*=vec[0].second; ans%=MOD;
return ans;
}
int init(int N, int X[], int Y[]) {
for(int i=0;i<MAXN*4;i++)seg2[i]=1;
while(offset<N)offset*=2;
for(int i=0;i<N;i++){
x.pb(X[i]); y.pb(Y[i]);
update(i,Y[i]);
update2(i,X[i]);
if(X[i]!=1)p.insert(i);
}
return (int)sol();
}
int updateX(int pos, int val) {
if(x[pos]==1 && val!=1)p.insert(pos);
if(x[pos]!=1 && val==1)p.erase(pos);
x[pos]=val;
update2(pos,x[pos]);
return (int)sol();
}
int updateY(int pos, int val) {
y[pos]=val;
update(pos,val);
return (int)sol();
}
