#include <bits/stdc++.h>
using namespace std;
#include "horses.h"
int n; long long mod=1e9+7,inf=1e9+1;
using segtype = tuple<long long,long long,long long,long long,int,long long>;
// answer mod,min(answer,1e9+1),min(width,1e9+1),min(answer_width,1e9+1),max_value,width mod
vector<segtype> segtree;
segtype f(segtype x,segtype y){
auto [a,b,c,d,e,k] = x; auto [f,g,h,i,j,l] = y;
if (e>=d*g) return make_tuple(a,b,min(c*h,inf),min(d*h,inf),e,(k*l)%mod);
return make_tuple((f*k)%mod,min(b*k,inf),min(c*h,inf),i,j,(k*l)%mod);
}
segtype id = make_tuple(0,0,1,1,0,1);
int res(){
segtype ll = id,rr = id;
for (int l(n),r(n+n);l < r;l>>=1,r>>=1){
if (l&1) ll = f(ll,segtree[l++]);
if (r&1) rr = f(segtree[--r],rr);
}
return get<0>(f(ll,rr));
}
int init(int nn,int A[],int B[]){
n = nn,segtree.assign(2*n,id),swap(A,B);
for (int i(0);i < n;++i) segtree[n+i] = make_tuple(
((long long)A[i]*B[i])%mod,
min((long long)A[i]*B[i],inf),
B[i],
1,
A[i],
B[i]
);
for (int i(n-1);i;--i) segtree[i] = f(segtree[i<<1],segtree[i<<1|1]);
return res();
}
int updateX(int x,int y){
int z = get<4>(segtree[n+x]);
segtree[n+x] = make_tuple( ((long long)y*z)%mod, min((long long)y*z,inf), y, 1, z, y );
for (int l((n+x)>>1);l;l>>=1) segtree[l] = f(segtree[l<<1],segtree[l<<1|1]);
return res();
}
int updateY(int x,int y){
int z = get<5>(segtree[n+x]); swap(y,z);
segtree[n+x] = make_tuple( ((long long)y*z)%mod, min((long long)y*z,inf), y, 1, z, y );
for (int l((n+x)>>1);l;l>>=1) segtree[l] = f(segtree[l<<1],segtree[l<<1|1]);
return res();
}
