#include <stdio.h>
#include <stdlib.h>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int def = 5e5+1;
const ll mod = 1e9+7;
ll powmod(ll a, ll b){
if (b == 0)
return 1;
if (b % 2 == 0){
ll val = powmod(a, b / 2);
return (val * val) % mod;
}
else
return (a * powmod(a, b - 1)) % mod;
}
ll inv(ll x){
return powmod(x, mod - 2);
}
ll bit[def];
void apply(int u, ll val){
for (int i = u; i < def; i += i & -i)
(bit[i] *= val) %= mod;
}
ll query(int u){
ll res = 1;
for (int i = u; i > 0; i -= i & -i)
(res *= bit[i]) %= mod;
return res;
}
struct SegmentTree{
vector<int> st;
int n;
SegmentTree(int n) : n(n){
st = vector<int>(4 * n, 0);
}
void update(int l, int r, int crr, int i, int v){
if (l > i || r < i)
return;
if (l == r){
st[crr] = v;
return;
}
int mid = (l + r) / 2;
update(l, mid, crr * 2 + 1, i, v);
update(mid + 1, r, crr * 2 + 2, i, v);
st[crr] = max(st[crr * 2 + 1], st[crr * 2 + 2]);
}
int get(int l, int r, int ql, int qr, int crr){
if (qr < l || ql > r)
return 0;
if (l >= ql && r <= qr)
return st[crr];
int mid = (l + r) / 2;
return max(get(l, mid, ql, qr, crr * 2 + 1), get(mid + 1, r, qr, qr, crr * 2 + 2));
}
};
SegmentTree st1(def);
SegmentTree st2(def);
ll x[def], y[def];
int n;
int get(){
int l = n;
__int128_t crr = 1;
vector<int> pos;
while (l > 0){
int nxt = st1.get(0, def - 1, 0, l - 1, 0);
if (nxt == 0){
pos.push_back(0);
break;
}
if (crr * x[nxt - 1] > 1e18){
if (nxt != l)
pos.push_back(nxt);
break;
}
pos.push_back(nxt - 1);
crr *= x[nxt - 1];
l = nxt - 1;
}
ll prefix = query(l);
__int128_t best = 1;
crr = 1;
reverse(pos.begin(), pos.end());
for (int i = 0; i < pos.size(); i++){
crr *= x[pos[i]];
int nxt = n;
if (i + 1 < pos.size())
nxt = pos[i + 1];
ll maxy = st2.get(0, def - 1, pos[i], nxt - 1, 0);
best = max(best, crr * maxy);
}
best %= mod;
ll res = (prefix * best) % mod;
return res;
}
int init(int N, int X[], int Y[]){
n = N;
for (int i = 0; i < def; i++)
bit[i] = 1;
for (int i = 0; i < n; i++){
x[i] = X[i];
if (x[i] > 1)
st1.update(0, def - 1, 0, i, i + 1);
apply(i + 1, x[i]);
y[i] = Y[i];
st2.update(0, def - 1, 0, i, y[i]);
}
return get();
}
int updateX(int pos, int val){
apply(pos + 1, ((ll)inv(x[pos]) * (ll)val) % mod);
x[pos] = val;
if (x[pos] > 1)
st1.update(0, def - 1, 0, pos, pos + 1);
else
st1.update(0, def - 1, 0, pos, 0);
return get();
}
int updateY(int pos, int val){
y[pos] = val;
st2.update(0, def - 1, 0, pos, y[pos]);
return get();
}
