#include <bits/stdc++.h>
using namespace std;
#include "horses.h"
// #define ll long long
// #define long long long long
const long long N = 5e5 + 5, M = 1e9 + 7;
long long n, cur, x[N], y[N];
struct node {
long long mxy, px;
long long left = -1, right = -1;
};
vector<node> T;
set<long long> st;
node join(node a, node b){
node ans;
ans.px = (a.px * b.px) % M;
ans.mxy = max(a.mxy, b.mxy);
return ans;
}
void build (long long v = 1, long long s = 0, long long e = n){
if (e - s == 1){
T[v].mxy = y[s];
T[v].px = x[s];
if (x[s] != 1) st.insert(s);
return;
}
T[v].left = ++cur;
T.push_back(node());
T[v].right = ++cur;
T.push_back(node());
long long lc = T[v].left, rc = T[v].right, mid = (s + e) / 2;
build(lc, s, mid);
build(rc, mid, e);
T[v] = join(T[lc], T[rc]);
}
node query(long long l, long long r, long long v = 1, long long s = 0, long long e = n){
if (l <= s && e <= r){
return T[v];
}
if (r <= s or e <= l){
node temp = node();
return temp;
}
long long mid = (s + e) / 2, lc = T[v].left, rc = T[rc].right;
if (r > mid){
node ans = query(l, r, rc, mid, e);
if (l < mid){
ans = join(ans, query(l, r, lc, s, mid));
}
return ans;
}
return query(l, r, lc, s, mid);
}
void updx(long long pos, long long val, long long v = 1, long long s = 0, long long e = n){
if (pos < s or e <= pos){
return;
}
if (e - s == 1){
T[v].px = val;
return;
}
long long mid = (s + e) / 2, lc = T[v].left, rc = T[v].right;
updx(pos, val, lc, s, mid);
updx(pos, val, rc, mid, e);
T[v] = join(T[lc], T[rc]);
}
void updy(long long pos, long long val, long long v = 1, long long s = 0, long long e = n){
if (pos < s or e <= pos){
return;
}
if (e - s == 1){
T[v].mxy = val;
return;
}
long long mid = (s + e) / 2, lc = T[v].left, rc = T[v].right;
updx(pos, val, lc, s, mid);
updx(pos, val, rc, mid, e);
T[v] = join(T[lc], T[rc]);
}
int init(int N, int X[], int Y[]){
n = N;
for (long long i = 0; i < n; i++){
x[i] = X[i];
y[i] = Y[i];
}
T.push_back(node());
build();
if (st.empty()){
return query(0, n).mxy;
}
auto it = --st.end();
long long pd = *it;
while (pd <= 1e9 && it != st.begin()){
it--;
pd *= x[*it];
}
long long ans = 1;
if (pd > 1e9){
pd /= x[*it];
ans = query(*it, n).mxy;
it++;
}
if (it == st.begin()){
ans = query(0, *it).mxy;
}
long long cf = query(0, *it).px, prod = 1;
while (it != st.end()){
prod *= x[*it];
ans = max(ans, prod * query(*it, n).mxy);
it++;
}
return (((ans % M) * cf) % M);
}
int updateX(int pos, int val){
if (x[pos] != 1) st.erase(pos);
x[pos] = val;
updx(pos, val);
if (x[pos] != 1) st.insert(pos);
if (st.empty()){
return query(0, n).mxy;
}
auto it = --st.end();
long long pd = *it;
while (pd <= 1e9 && it != st.begin()){
it--;
pd *= x[*it];
}
long long ans = 1;
if (pd > 1e9){
pd /= x[*it];
ans = query(*it, n).mxy;
it++;
}
if (it == st.begin()){
ans = query(0, *it).mxy;
}
long long cf = query(0, *it).px, prod = 1;
while (it != st.end()){
prod *= x[*it];
ans = max(ans, prod * query(*it, n).mxy);
it++;
}
return (((ans % M) * cf) % M);
}
int updateY(int pos, int val){
updy(pos, val);
if (st.empty()){
return query(0, n).mxy;
}
auto it = --st.end();
long long pd = *it;
while (pd <= 1e9 && it != st.begin()){
it--;
pd *= x[*it];
}
long long ans = 1;
if (pd > 1e9){
pd /= x[*it];
ans = query(*it, n).mxy;
it++;
}
if (it == st.begin()){
ans = query(0, *it).mxy;
}
long long cf = query(0, *it).px, prod = 1;
while (it != st.end()){
prod *= x[*it];
ans = max(ans, prod * query(*it, n).mxy);
it++;
}
return (((ans % M) * cf) % M);
}
