#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
const ll MOD = 1e9+7;
const ll INF = 4e18;
#define bg(x) (x).begin()
#define en(x) (x).end()
#define all(x) (x).begin(), (x).end()
#define sz(x) (int((x).size()))
#define f first
#define s second
#define pb push_back
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define rev(i, a, b) for (int i = a; i >= b; i--)
template<class T> bool chmax(T& a, const T& b) {return a < b ? a = b, 1 : 0;}
template<class T> bool chmin(T& a, const T& b) {return b < a ? a = b, 1 : 0;}
#ifdef LOCAL
#define dbg(x) cerr << #x << " = " << x << "\n"
#else
#define dbg(x)
#endif
ll modexp(ll a, ll b) {
if (b <= 0) return 1LL;
if (b == 1) return a % MOD;
ll r = modexp(a, b/2);
r = (r*r) % MOD;
if (b%2==1) r = (r*a)%MOD;
return r%MOD;
}
ll inv(ll m) {
return modexp(m, MOD-2);
}
struct Fenw {
int n; vl BIT;
Fenw(int n = 0) : n(n), BIT(n, 1) {}
ll query(int r) {
ll res = 1; for (; r >= 0; r &= r+1, r--) res = (res * BIT[r]) % MOD;
return res;
}
ll point_query(int i) {
ll a = query(i-1), b = query(i);
return (inv(a) * b) % MOD;
}
void update(int i, ll delta) {
for (; i < n; i |= i+1) BIT[i] = (BIT[i] * delta) % MOD;
}
void set(int i, ll v) {
update(i, inv(point_query(i)));
update(i, v % MOD);
}
};
struct SegTree {
int n; vl arr, st;
SegTree() {}
SegTree(int N, vl &Arr) {
n = N; arr = Arr; st.assign(4*n, INT_MIN);
build(0, 0, n);
}
int build(int i, int l, int r) {
if (l+1==r) return st[i] = arr[l];
int m = l + (r-l) / 2;
return st[i] = max(build(2*i+1, l, m), build(2*i+2,m,r));
}
int update(int i, int l, int r, int k, int v) {
if (!(l <= k && k < r)) return st[i];
if (l+1==r) return st[i] = arr[k] = v;
int m = l + (r-l) / 2;
return st[i] = max(update(2*i+1, l, m, k, v), update(2*i+2,m,r, k, v));
}
int query(int i, int l, int r, int ql, int qr) {
if (qr <= l || r <= ql) return INT_MIN;
if (ql <= l && r <= qr) return st[i];
if (l+1==r) return arr[l];
int m = l + (r-l) / 2;
return max(query(2*i+1, l, m, ql, qr), query(2*i+2,m,r, ql, qr));
}
};
int n;
vl x, y;
Fenw fenwx;
SegTree sty;
set<int> notone;
int compute() {
ll ans = x[n-1] * y[n-1];
bool didmod = ans >= MOD;
ans %= MOD;
if (notone.empty()) {
return sty.query(0, 0, n, 0, n);
}
auto it = notone.rbegin();
if (*it == n-1) ++it;
int prev = n-1;
// rev(i, n-2, 0) {
while (it != notone.rend()) {
int i = *it;
int best = sty.query(0, 0, n, i+1, prev);
if (!didmod && best > ans) ans = best;
ans *= x[i];
didmod = didmod || (ans >= MOD);
ans %= MOD;
if (didmod) {
ans = (fenwx.query(i-1) * ans) % MOD;
break;
}
prev = i;
++it;
}
return ans % MOD;
}
int init(int N, int X[], int Y[]) {
n = N; x.assign(X, X+N); y.assign(Y, Y+N);
fenwx = Fenw(n); sty = SegTree(n, y);
for (int i = 0; i < n; i++) fenwx.set(i, x[i]);
for (int i = 0; i < n; i++) if (x[i] != 1) notone.insert(i);
notone.insert(-1);
return compute();
}
int updateX(int pos, int val) {
x[pos] = val; fenwx.set(pos, val);
if (val == 1) notone.erase(pos);
else notone.insert(pos);
return compute();
}
int updateY(int pos, int val) {
y[pos] = val; sty.update(0, 0, n, pos, val);
return compute();
}
