#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define fs first
#define sc second
const ll mod = 1e9+7;
const ll mxn = 5e5+10;
int N;
int arr[mxn],brr[mxn];
set<int> st;
struct SEG{
#define ls now*2+1
#define rs now*2+2
#define mid ((l+r)>>1)
int mx[mxn*4];
ll seg[mxn*4];
void build(int now,int l,int r){
if(l == r){
seg[now] = arr[l];
mx[now] = brr[l];
return;
}
build(ls,l,mid);
build(rs,mid+1,r);
mx[now] = max(mx[ls],mx[rs]);
seg[now] = seg[ls]*seg[rs];
if(seg[now]>=mod)seg[now] = mod+seg[now]%mod;
return;
}
void modify(int now,int l,int r,int p){
if(l == r){
seg[now] = arr[l];
mx[now] = brr[l];
return;
}
if(mid>=p)modify(ls,l,mid,p);
else modify(rs,mid+1,r,p);
mx[now] = max(mx[ls],mx[rs]);
seg[now] = seg[ls]*seg[rs];
if(seg[now]>=mod)seg[now] = mod+seg[now]%mod;
}
ll getsum(int now,int l,int r,int s,int e){
if(l>=s&&e>=r)return seg[now];
if(mid>=e)return getsum(ls,l,mid,s,e);
else if(mid<s)return getsum(rs,mid+1,r,s,e);
else{
auto re = getsum(ls,l,mid,s,e)*getsum(rs,mid+1,r,s,e);
if(re>=mod)return mod+re%mod;
else return re;
}
}
ll getmax(int now,int l,int r,int s,int e){
if(l>=s&&e>=r)return mx[now];
if(mid>=e)return getmax(ls,l,mid,s,e);
else if(mid<s)return getmax(rs,mid+1,r,s,e);
else return max(getmax(ls,l,mid,s,e),getmax(rs,mid+1,r,s,e));
}
#undef ls
#undef rs
#undef mid
};
SEG seg;
bool cmp(int a,int b){
if(a>b)return seg.getmax(0,0,N-1,a,N-1)*seg.getsum(0,0,N-1,b+1,a)<seg.getmax(0,0,N-1,b,N-1);
else return seg.getmax(0,0,N-1,a,N-1)<seg.getmax(0,0,N-1,b,N-1)*seg.getsum(0,0,N-1,a+1,b);
}
ll getans(){
st.insert(0);
vector<int> v;
ll pref = 1;
for(auto it = st.rbegin();it != st.rend()&&pref<mod;it++){
v.push_back(*it);
pref *= arr[*it];
}
sort(v.begin(),v.end(),cmp);
int tar = v.back();
return seg.getmax(0,0,N-1,tar,N-1)*seg.getsum(0,0,N-1,0,tar)%mod;
}
int init(int NN, int X[], int Y[]) {
N = NN;
for(int i = 0;i<N;i++){
arr[i] = X[i];
if(arr[i] != 1)st.insert(i);
brr[i] = Y[i];
}
seg.build(0,0,N-1);
//cerr<<"INIT! "<<seg.getmax(0,0,N-1,0,N-1)<<endl;
return getans();
}
int updateX(int pos, int val) {
arr[pos] = val;
if(arr[pos] == 1&&st.find(pos) != st.end())st.erase(pos);
else if(arr[pos] != 1)st.insert(pos);
seg.modify(0,0,N-1,pos);
return getans();
}
int updateY(int pos, int val) {
brr[pos] = val;
seg.modify(0,0,N-1,pos);
return getans();
}
