#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define debug(x) cout << #x << " => " << x << "\n";
const long long mod = 1e9 + 7;
ll n, x[500005], y[500005];
struct node {
ll idx, val, nxt, prv;
} arr[500005];
set <ll> st;
ll tree[2000005];
void upd(ll idx, ll l, ll r, ll x, ll v) {
if(l == r) {
tree[idx] = v;
return;
}
ll mid = (l + r) / 2;
if(x <= mid) upd(idx * 2, l, mid, x, v);
else upd(idx * 2 + 1, mid + 1, r, x, v);
tree[idx] = (tree[idx * 2] * tree[idx * 2 + 1]) % mod;
}
ll query(ll idx, ll l, ll r, ll x, ll y) {
if(l > r || l > y || r < x) return 1;
if(l >= x && r <= y) return tree[idx];
ll mid = (l + r) / 2;
return (query(idx * 2, l, mid, x, y) * query(idx * 2 + 1, mid + 1, r, x, y)) % mod;
}
ll maxy[2000005];
void updy(ll idx, ll l, ll r, ll x, ll v) {
if(l == r) {
maxy[idx] = v;
return;
}
ll mid = (l + r) / 2;
if(x <= mid) updy(idx * 2, l, mid, x, v);
else updy(idx * 2 + 1, mid + 1, r, x, v);
maxy[idx] = max(maxy[idx * 2], maxy[idx * 2 + 1]);
}
ll queryy(ll idx, ll l, ll r, ll x, ll y) {
if(l > r || l > y || r < x) return 0;
if(l >= x && r <= y) return maxy[idx];
ll mid = (l + r) / 2;
return max(queryy(idx * 2, l, mid, x, y), queryy(idx * 2 + 1, mid + 1, r, x, y));
}
int init(int N, int X[], int Y[]) {
n = N;
for(ll i = 1; i <= n; i++) {
x[i] = X[i - 1];
y[i] = Y[i - 1];
upd(1, 1, n, i, x[i]);
updy(1, 1, n, i, y[i]);
}
for(ll i = 1; i <= n; i++) {
if(x[i] > 1) {
st.insert(i);
}
}
x[n + 1] = 1;
st.insert(n + 1);
x[0] = 1;
st.insert(0);
auto it = st.end();
pair <ll,ll> maxi = {0, 0};
vector <ll> tmp;
for(ll mul = 1; it != st.begin();) {
it--;
mul *= x[*it];
tmp.pb(*it);
if(mul > 1e9) break;
}
reverse(tmp.begin(), tmp.end());
for(ll i = 0, mul = 1; i < tmp.size() - 1; i++) {
ll max_y = queryy(1, 1, n, tmp[i], tmp[i + 1] - 1);
maxi = max(maxi, {mul * max_y, tmp[i]});
mul *= x[tmp[i + 1]];
}
auto nuit = st.upper_bound(maxi.se);
return (query(1, 1, n, 1, maxi.se) * queryy(1, 1, n, maxi.se, *nuit - 1)) % mod;
}
int updateX(int pos, int val) {
pos++;
x[pos] = val;
if(x[pos] == 1) st.erase(pos);
else st.insert(pos);
upd(1, 1, n, pos, val);
auto it = st.end();
pair <ll,ll> maxi = {0, 0};
vector <ll> tmp;
for(ll mul = 1; it != st.begin();) {
it--;
mul *= x[*it];
tmp.pb(*it);
if(mul > 1e9) break;
}
reverse(tmp.begin(), tmp.end());
for(ll i = 0, mul = 1; i < tmp.size() - 1; i++) {
ll max_y = queryy(1, 1, n, tmp[i], tmp[i + 1] - 1);
maxi = max(maxi, {mul * max_y, tmp[i]});
mul *= x[tmp[i + 1]];
}
auto nuit = st.upper_bound(maxi.se);
return (query(1, 1, n, 1, maxi.se) * queryy(1, 1, n, maxi.se, *nuit - 1)) % mod;
}
int updateY(int pos, int val) {
pos++;
y[pos] = val;
updy(1, 1, n, pos, val);
auto it = st.end();
pair <ll,ll> maxi = {0, 0};
vector <ll> tmp;
for(ll mul = 1; it != st.begin();) {
it--;
mul *= x[*it];
tmp.pb(*it);
if(mul > 1e9) break;
}
reverse(tmp.begin(), tmp.end());
for(ll i = 0, mul = 1; i < tmp.size() - 1; i++) {
ll max_y = queryy(1, 1, n, tmp[i], tmp[i + 1] - 1);
maxi = max(maxi, {mul * max_y, tmp[i]});
mul *= x[tmp[i + 1]];
}
auto nuit = st.upper_bound(maxi.se);
return (query(1, 1, n, 1, maxi.se) * queryy(1, 1, n, maxi.se, *nuit - 1)) % mod;
}
// static char _buffer[1024];
// static int _currentChar = 0;
// static int _charsNumber = 0;
// static FILE *_inputFile, *_outputFile;
// static inline int _read() {
// if (_charsNumber < 0) {
// exit(1);
// }
// if (!_charsNumber || _currentChar == _charsNumber) {
// _charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), _inputFile);
// _currentChar = 0;
// }
// if (_charsNumber <= 0) {
// return -1;
// }
// return _buffer[_currentChar++];
// }
// static inline int _readInt() {
// int c, x, s;
// c = _read();
// while (c <= 32) c = _read();
// x = 0;
// s = 1;
// if (c == '-') {
// s = -1;
// c = _read();
// }
// while (c > 32) {
// x *= 10;
// x += c - '0';
// c = _read();
// }
// if (s < 0) x = -x;
// return x;
// }
// int main() {
// // _inputFile = fopen("horses.in", "rb");
// // _outputFile = fopen("horses.out", "w");
// int N; cin >> N;
// int *X = (int*)malloc(sizeof(int)*(unsigned int)N);
// int *Y = (int*)malloc(sizeof(int)*(unsigned int)N);
// for (int i = 0; i < N; i++) {
// cin >> X[i];
// }
// for (int i = 0; i < N; i++) {
// cin >> Y[i];
// }
// // fprintf(_outputFile,"%d\n",init(N,X,Y));
// cout << init(N, X, Y) << "\n";
// int M; cin >> M;
// for (int i = 0; i < M; i++) {
// int type; cin >> type;
// int pos; cin >> pos;
// int val; cin >> val;
// if (type == 1) {
// cout << updateX(pos, val) << "\n";
// } else if (type == 2) {
// cout << updateY(pos, val) << "\n";
// }
// }
// return 0;
// }
// int main() {
// // _inputFile = fopen("horses.in", "rb");
// // _outputFile = fopen("horses.out", "w");
// int N; cin >> N;
// int *X = (int*)malloc(sizeof(int)*(unsigned int)N);
// int *Y = (int*)malloc(sizeof(int)*(unsigned int)N);
// for (int i = 0; i < N; i++) {
// cin >> X[i];
// }
// for (int i = 0; i < N; i++) {
// cin >> Y[i];
// }
// // fprintf(_outputFile,"%d\n",init(N,X,Y));
// int M; cin >> M;
// for (int i = 0; i < 7; i++) {
// int type; cin >> type;
// int pos; cin >> pos;
// int val; cin >> val;
// if (type == 1) {
// X[pos] = val;
// } else if (type == 2) {
// Y[pos] = val;
// }
// }
// cout << init(N, X, Y) << "\n";
// return 0;
// }
