#include <bits/stdc++.h>
using namespace std;
//#include "horses.h"
#define ll long long
#define MOD 1000000007
set<ll> multiIndices;
int mainX[500007], mainY[500007];
struct node{
ll mx;
ll product;
ll s, e, m;
node *l, *r;
node(int x, int y, bool readFromX){
s = x, e = y; m = (s+e)/2;
if (s != e){
l = new node(x, m, readFromX);
r = new node(m+1, y, readFromX);
}
else if (readFromX){
product = mainX[s];
mx = mainX[s];
return;
}
else {
product = mainY[s];
mx = mainY[s];
return;
}
mx = max(l->mx, r->mx);
product = (l->product * r->product)%MOD;
}
void update(int idx, ll val){
if (s == e){
product = val;
mx = val;
return;
}
else if (idx <= m) l->update(idx, val);
else r->update(idx, val);
mx = max(l->mx, r->mx);
product = (l->product * r->product)%MOD;
}
ll productQuery(int x, int y){
if (x <= s && y >= e){
return product; //entirely contained
}
if (y <= m){
return l->productQuery(x, y);
}
if (x >= m+1){
return r->productQuery(x, y);
}
return (l->productQuery(x, m) * r->productQuery(m+1, y))%MOD;
}
ll maxQuery(int x, int y){
if (x <= s && y >= e){
return mx; //entirely contained
}
if (y <= m){
return l->maxQuery(x, y);
}
if (x >= m+1){
return r->maxQuery(x, y);
}
return max(l->maxQuery(x, m), r->maxQuery(m+1, y));
}
};
int n;
node *repro;
node *sellPrice;
ll calc(){
vector<int> indices;
auto iter = multiIndices.rbegin();
for (int x = 0; x < 32; x++){
if (iter == multiIndices.rend()) break;
indices.push_back(*iter);
iter++;
}
if (indices.size() == 0 || indices.back() != 0) indices.push_back(0);
reverse(indices.begin(), indices.end());
indices.push_back(n);
//cout << "\n";
//for (int i : indices) cout << i << ' ';
//cout << "\n";
ll ansLoc = 0;
ll ans = (sellPrice->maxQuery(0, indices[1] - 1) * repro->productQuery(0, 0))%MOD;
ll multiplier = 1;
for (int x = 1; x < indices.size() - 1; x++){
//cout << repro->productQuery(0, indices[x]) << ' ' << sellPrice->maxQuery(indices[x], indices[x+1] - 1) << "\n\n\n";
multiplier *= repro->productQuery(indices[x], indices[x]);
ll sp = sellPrice->maxQuery(indices[x], indices[x+1] - 1);
if (multiplier >= 1000000000 || ans <= multiplier * sp){
ans = sp; multiplier = 1; ansLoc = x;
}
//ans = max(ans, (repro->productQuery(0, indices[x]) * sellPrice->maxQuery(indices[x], indices[x+1] - 1))%MOD);
//oh this is wrong lmaooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
}
return (repro->productQuery(0, indices[ansLoc]) * sellPrice->maxQuery(indices[ansLoc], indices[ansLoc+1] - 1))%MOD;
}
int updateX(int pos, int val) {
if (mainX[pos] > 1) multiIndices.erase(multiIndices.find(pos));
mainX[pos] = val;
repro->update(pos, val);
if (mainX[pos] > 1) multiIndices.insert(pos);
return calc();
}
int updateY(int pos, int val) {
mainY[pos] = val;
sellPrice->update(pos, val);
return calc();
}
int init(int N, int X[], int Y[]) {
n = N;
for (int x = 0; x < N; x++) { mainX[x] = X[x]; if (X[x] > 1) multiIndices.insert(x);}
for (int x = 0; x < N-1; x++) { mainY[x] = Y[x];}
repro = new node(0, N, 1);
sellPrice = new node(0, N, 0);
return updateY(N-1, Y[N-1]);
}
