#include "horses.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef pair<int,int> ii;
const ll mod = (ll) 1e9+7;
struct segTreeMul{
ll node[2000005];
segTreeMul(){
for(int i=1;i<=2000000;i++) node[i] = 1;
}
void upd(int id,int l,int r,int pos,int val){
if (r < pos || pos < l) return;
if (l == r){
node[id] = val;
return;
}
upd(2*id,l,(l+r)/2,pos,val);
upd(2*id+1,(l+r)/2+1,r,pos,val);
node[id] = node[2*id] * node[2*id+1] % mod;
}
ll get(int id,int l,int r,int u,int v){
if (r < u || v < l) return 1;
if (u <= l && r <= v) return node[id];
return get(2*id, l, (l+r)/2, u, v) * get(2*id+1, (l+r)/2+1, r, u, v) % mod;
}
};
struct segTreeMax{
ll node[2000005];
segTreeMax(){
for(int i=1;i<=2000000;i++) node[i] = -1;
}
void upd(int id,int l,int r,int pos,int val){
if (r < pos || pos < l) return;
if (l == r){
node[id] = val;
return;
}
upd(2*id,l,(l+r)/2,pos,val);
upd(2*id+1,(l+r)/2+1,r,pos,val);
node[id] = max(node[2*id], node[2*id+1]);
}
ll get(int id,int l,int r,int u,int v){
if (r < u || v < l) return 1;
if (u <= l && r <= v) return node[id];
return max(get(2*id, l, (l+r)/2, u, v), get(2*id+1, (l+r)/2+1, r, u, v));
}
};
segTreeMul segMul;
segTreeMax segMax;
int n;
int growthNum[500005];
set <int> notOneLst;
ll getBest(){
if (notOneLst.empty())
return segMax.get(1,1,n,1,n);
vector <int> importants;
importants.push_back(n+1);
set<int>::iterator it = notOneLst.end();
ll prod = 1;
while(it != notOneLst.begin() && prod < mod){
it --;
importants.push_back(*it);
prod *= growthNum[*it];
}
if (prod < mod && importants[0] != 1)
importants.push_back(1);
//reverse(importants.begin(), importants.end());
double bestRatio = 0;
int bestPos = -1;
ll denominator = 1;
for(int i=1;i<importants.size();i++){
ll ma = segMax.get(1,1,n,importants[i], importants[i-1]-1);
if (1.0 * ma / denominator > bestRatio){
bestPos = i;
bestRatio = 1.0 * ma / denominator;
}
denominator *= growthNum[importants[i]];
}
return segMul.get(1,1,n,1,importants[bestPos]) * segMax.get(1,1,n,importants[bestPos], importants[bestPos-1]-1) % mod;
}
int init(int N, int X[], int Y[]) {
n = N;
for(int i=0;i<n;i++){
growthNum[i+1] = X[i];
if (growthNum[i+1] > 1)
notOneLst.insert(i+1);
segMul.upd(1,1,n,i+1,X[i]);
}
for(int i=0;i<n;i++){
segMax.upd(1,1,n,i+1,Y[i]);
}
return getBest();
}
int updateX(int pos, int val) {
pos++;
if (growthNum[pos] > 1) notOneLst.erase(pos);
growthNum[pos] = val;
segMul.upd(1,1,n,pos,val);
if (growthNum[pos] > 1) notOneLst.insert(pos);
return getBest();
}
int updateY(int pos, int val) {
pos++;
segMax.upd(1,1,n,pos,val);
return getBest();
}
