#include <bits/stdc++.h>
using namespace std;
//#include "grader.cpp"
#include "horses.h"
const int mod=(1e9)+7,MAXN=500005;
int add(int a,int b){
a+=b;
if(a>=mod)a-=mod;
return a;
}
int sub(int a,int b){
a-=b;
if(a<0)a+=mod;
return a;
}
int mul(int a,int b){
return(a*1LL*b)%mod;
}
int power(int x,int n){
int res=1;
while(n){
if(n&1)res=mul(res,x);
x=mul(x,x);
n>>=1;
}
return res;
}
int inv(int a){
return power(a,mod-2);
}
int divide(int a,int b){
return mul(a,inv(b));
}
int x[MAXN],y[MAXN],n;
set<int>not_one;
int bit[MAXN],tree[1<<20];
void upd(int i,int val){
for(;i<=n;i+=i&-i)bit[i]=mul(bit[i],val);
}
int qry(int i){
int res=1;
for(;i>=1;i-=i&-i)res=mul(res,bit[i]);
return res;
}
void update(int l,int r,int p,int idx,int val){
if(l==r){
tree[p]=val;
return;
}
int md=(l+r)>>1;
if(md>=idx)update(l,md,p*2+1,idx,val);
else update(md+1,r,p*2+2,idx,val);
tree[p]=max(tree[p*2+1],tree[p*2+2]);
}
int query(int l,int r,int p,int l_q,int r_q){
if(l>r_q||r<l_q)return 0;
if(l>=l_q&&r<=r_q)return tree[p];
int md=(l+r)>>1;
return max(query(l,md,p*2+1,l_q,r_q),query(md+1,r,p*2+2,l_q,r_q));
}
int solve(){
long long cur_factor=1,all_factor=1;
int last=n+1;
long long ans=0,best=0;
for(auto it=not_one.rbegin();it!=not_one.rend();it++){
int cur_pos=*it;
int cur_y=query(1,n,0,cur_pos,last-1);
if(cur_y>best*cur_factor) {
best=cur_y;
ans=mul(qry(cur_pos),cur_y);
cur_factor=1;
}
cur_factor*=x[cur_pos];
all_factor*=x[cur_pos];
if(all_factor>mod)break;
last=cur_pos;
}
return ans;
}
int init(int N, int X[], int Y[]) {
n=N;
x[0]=y[0]=1;
for(int i=1;i<=n;i++)x[i]=X[i-1],y[i]=Y[i-1];
for(int i=0;i<=n;i++)bit[i]=1;
for(int i=1;i<=n;i++){
upd(i,x[i]);
update(1,n,0,i,y[i]);
}
for(int i=1;i<=n;i++){
if(x[i]>1)not_one.insert(i);
}
not_one.insert(1);
return solve();
}
int updateX(int pos,int val){
pos++;
upd(pos,divide(val,x[pos]));
if(x[pos]>1&&pos>1)not_one.erase(pos);
x[pos]=val;
if(x[pos]>1)not_one.insert(pos);
return solve();
}
int updateY(int pos,int val){
pos++;
y[pos]=val;
update(1,n,0,pos,val);
return solve();
}
