#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
//typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef __int128 ll;
typedef vector<ll> vl;
const ll MOD = 1e9+7;
struct SegMx {
int n;
vl t;
SegMx(int sz = 0) {
n = sz;
t.resize(2*n);
}
ll query(int l, int r) {
ll ret = 0;
for (l += n, r += n; l < r; l /= 2, r /= 2) {
if (l&1) ret = max(ret, t[l++]);
if (r&1) ret = max(ret, t[--r]);
}
return ret;
}
void update(int p, ll v) {
for (t[p += n] = v; p > 1; p /= 2) t[p/2] = max(t[p], t[p^1]);
}
};
struct SegMult {
int n;
vl t;
SegMult(int sz = 0) {
n = sz;
t.resize(2*n, 1);
}
ll query(int l, int r) {
ll ret = 1;
for (l += n, r += n; l < r; l /= 2, r /= 2) {
if (l&1) ret = (ret*t[l++])%MOD;
if (r&1) ret = (ret*t[--r])%MOD;
}
return ret;
}
void update(int p, ll v) {
for (t[p += n] = v; p > 1; p /= 2) t[p/2] = (t[p]+t[p^1])%MOD;
}
};
int n;
SegMx ty;
SegMult tx;
set<int> non1{0};
int calc() {
vi p;
auto it = prev(non1.end());
ll tot = 1;
for (int i = 0; i < 60; i++) {
p.push_back(*it);
tot *= tx.t[n+p.back()];
//cout << (long long)tot << " " << i << endl;
if (tot > (ll)1e18) break;
if (it == non1.begin()) break;
it = prev(it);
}
reverse(p.begin(), p.end());
//for (int i : p) cout << i << " "; cout << endl;
int m = (int)p.size();
p.push_back(n);
ll base = p[0] ? tx.query(0, p[0])%MOD : 1;
ll mult = 1;
ll mx = 0;
for (int i = 0; i < m; i++) {
int l = p[i], r = p[i+1];
ll y = ty.query(l, r);
mult *= tx.t[l+n];
mx = max(mx, y*mult);
}
//cout << (int)(((mx%MOD)*base)%MOD) << endl;
return (int)(((mx%MOD)*base)%MOD);
}
int init(int N, int x[], int y[]) {
n = N;
ty = SegMx(n);
tx = SegMult(n);
for (int i = 0; i < n; i++) {
if (x[i] > 1) non1.insert(i);
ty.update(i, y[i]);
tx.update(i, x[i]);
}
return calc();
}
int updateX(int i, int v) {
if (tx.t[i+n] > 1 && i) non1.erase(i);
tx.update(i, v);
if (tx.t[i+n] > 1 && i) non1.insert(i);
return calc();
}
int updateY(int i, int v) {
ty.update(i, v);
return calc();
}
