#include "horses.h"
#include <algorithm>
#include <vector>
#include <iostream>
#include <assert.h>
#include <set>
#define lc (i << 1)
#define rc (1 | (i << 1))
using namespace std;
const int MOD = 1e9 + 7;
int add(long long a, long long b){
return (a + b) % MOD;
}
int mul(long long a, long long b){
return (a * b) % MOD;
}
struct Node{
int val, mx;
Node(){
val = mx = 0;
}
};
Node st[4 * 500010];
int n;
vector<int> x, y;
const int MAX = 1e9;
void update(int l, int r, int pt, int val, int type, int i){
if(r < pt || pt < l) return;
if(l == r && l == pt){
if(type == 0) st[i].val = val;
else st[i].mx = val;
return;
}
int m = (l + r) >> 1;
update(l, m, pt, val, type, lc);
update(m + 1, r, pt, val, type, rc);
st[i].val = mul(st[lc].val, st[rc].val);
st[i].mx = max(st[lc].mx, st[rc].mx);
}
int query(int l, int r, int ls, int rs, int i){
if(r < ls || rs < l) return 1;
if(ls <= l && r <= rs) return st[i].val;
int m = (l + r) >> 1;
return mul(query(l, m, ls, rs, lc), query(m + 1, r, ls, rs, rc));
}
long long queryMax(int l, int r, int ls, int rs, int i){
if(r < ls || rs < l) return 0;
if(ls <= l && r <= rs) return st[i].mx;
int m = (l + r) >> 1;
return max(queryMax(l, m, ls, rs, lc), queryMax(m + 1, r, ls, rs, rc));
}
set<int> s;
int GetValue(){
int idx = 0;
long long pr = 1;
vector<int> path;
path.emplace_back(n);
auto it = s.end();
do {
it = prev(it);
path.emplace_back(*it);
} while (it != s.begin() || path.size() < 33);
for(int i = 1; i < (int) path.size(); i++){
pr *= x[path[i]];
if(pr > MAX) {
idx = i; break;
}
}
pr = 1;
int optVal = 0, opt = 0;
// int counter = 0;
for(int i = idx; i; i--){
int nxt = path[i - 1] - 1;
int cur_idx = max(0, path[i]);
pr *= x[cur_idx];
int yval = queryMax(0, n - 1, cur_idx, nxt, 1);
if(optVal < pr * yval){
opt = idx;
optVal = yval;
pr = 1;
}
}
return mul(query(0, n - 1, 0, opt, 1), optVal);
}
int init(int N, int X[], int Y[]) {
n = N;
x.insert(x.begin(), X, X + N);
y.insert(y.begin(), Y, Y + N);
for(int i = 0; i < n; i++) {
update(0, n - 1, i, x[i], 0, 1);
if(x[i] > 1) s.insert(i);
}
s.insert(-1);
for(int i = 0; i < n; i++) update(0, n - 1, i, y[i], 1, 1);
// for(int i = 0; i < n; i++){
// cerr << i << " with previous: " << GetPrev(i) << "\n";
// }
return GetValue();
}
int updateX(int pos, int val) {
if(x[pos] > 1 && val == 1) s.erase(pos);
else if (x[pos] == 1 && val > 1) s.insert(pos);
x[pos] = val;
update(0, n - 1, pos, val, 0, 1);
return GetValue();
}
int updateY(int pos, int val) {
y[pos] = val;
update(0, n - 1, pos, val, 1, 1);
return GetValue();
}
