#include "horses.h"
#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_multiset;
#define ll long long
#define ld long double
#define iloop(m, h) for (ll i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define lloop(m, h) for (auto l = m; l != h; l += (m < h ? 1 : -1))
#define iloop_(m, h, g) for (auto i = m; i != h; i += g)
#define jloop_(m, h, g) for (auto j = m; j != h; j += g)
#define kloop_(m, h, g) for (auto k = m; k != h; k += g)
#define lloop_(m, h, g) for (auto l = m; l != h; l += g)
#define getchar_unlocked _getchar_nolock // comment before submission
#define pll pair<ll, ll>
#define plll pair<ll, pll>
#define pllll pair<pll, pll>
#define vll vector<ll>
#define qll queue<ll>
#define dll deque<ll>
#define pqll priority_queue<ll>
#define gll greater<ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
set<ll> st;
ll n, x[500005], y[500005];
struct node {
ll s, e, m, px, mxy;
node *l, *r;
node (ll S, ll E) {
s = S, e = E, m = (S+E)>>1;
if (s == e) {
mxy = y[s];
px = x[s];
if (x[s] != 1) st.insert(s);
return;
}
l = new node(s, m);
r = new node(m+1, e);
px = (l->px * r->px)%MOD1;
mxy = max(l->mxy, r->mxy);
}
void updx(ll X, ll V) {
if (s == e) {px = V; return;}
if (X <= m) l->updx(X, V);
else r->updx(X, V);
px = (l->px * r->px)%MOD1;
}
void updy(ll X, ll V) {
if (s == e) {mxy = V; return;}
if (X <= m) l->updy(X, V);
else r->updy(X, V);
mxy = max(l->mxy, r->mxy);
}
ll qux(ll S, ll E) {
if (S > E) return 1;
if (s == S && e == E) return px;
if (E <= m) return l->qux(S, E);
if (S > m) return r->qux(S, E);
return (l->qux(S, m) * r->qux(m+1, E))%MOD1;
}
ll quy(ll S, ll E) {
if (S > E) return 1;
if (s == S && e == E) return mxy;
if (E <= m) return l->quy(S, E);
if (S > m) return r->quy(S, E);
return max(l->quy(S, m), r->quy(m+1, E));
}
} *root;
ll calc() {
if (!st.size()) return root->quy(0, n-1);
auto it = --st.end();
ll cpd = x[*it];
while (cpd <= 1e9 && it != st.begin()) {
it--;
cpd *= x[*it];
}
ll cans = 1, cprod = 1, cf = 1;
if (cpd > 1e9) {
cpd /= x[*it];
cans = root->quy(*it, n-1);
it++;
}
if (it == st.begin()) {
cans = root->quy(0, *it-1);
}
cf = root->qux(0, *it - 1);
while (it != st.end()) {
cprod *= x[*it];
cans = max(cans, cprod * root->quy(*it, n-1));
it++;
}
return ((cans%MOD1)*cf)%MOD1;
}
int init(int N, int X[], int Y[]) {
n = N;
iloop(0, n) x[i] = X[i], y[i] = Y[i];
root = new node(0, n-1);
return calc();
}
int updateX(int pos, int val) {
if (x[pos] != 1) st.erase(pos);
x[pos] = val;
root->updx(pos, val);
if (x[pos] != 1) st.insert(pos);
return calc();
}
int updateY(int pos, int val) {
root->updy(pos, val);
return calc();
}
