#include "horses.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(s) s.begin(), s.end()
#define pb push_back
#define fr first
#define sc second
#define vl vector < ll >
#define pl pair < ll, ll >
const int MN = 5e5 + 7;
const ll mod = 1e9 + 7;
ll t[4 * MN], m[4 * MN];
ll x[MN], y[MN], pr[MN];
set < int > p;
int n;
void build (int v, int l, int r){
if (l == r){
t[v] = x[l];
m[v] = y[l];
}
else {
int mid = (l + r) >> 1;
build(v + v, l, mid);
build(v + v + 1, mid + 1, r);
t[v] = (t[v + v] * t[v + v + 1]) % mod;
m[v] = max(m[v + v], m[v + v + 1]);
}
}
void upd (int v, int l, int r, int pos, ll val){
if (l == r)
t[v] = val;
else {
int mid = (l + r) >> 1;
if (pos <= mid)
upd(v + v, l, mid, pos, val);
else
upd(v + v + 1, mid + 1, r, pos, val);
t[v] = (t[v + v] * t[v + v + 1]) % mod;
}
}
void upd_m (int v, int l, int r, int pos, ll val){
if (l == r)
m[v] = val;
else {
int mid = (l + r) >> 1;
if (pos <= mid)
upd_m(v + v, l, mid, pos, val);
else
upd_m(v + v + 1, mid + 1, r, pos, val);
m[v] = max(m[v + v], m[v + v + 1]);
}
}
ll get (int v, int l, int r, int ql, int qr){
if (ql <= l && r <= qr)
return t[v];
if (r < ql || qr < l)
return 1LL;
int mid = (l + r) >> 1;
return (get(v + v, l, mid, ql, qr) * get(v + v + 1, mid + 1, r, ql, qr)) % mod;
}
ll get_m (int v, int l, int r, int ql, int qr){
if (ql <= l && r <= qr)
return m[v];
if (r < ql || qr < l)
return 1LL;
int mid = (l + r) >> 1;
return max(get_m(v + v, l, mid, ql, qr), get_m(v + v + 1, mid + 1, r, ql, qr));
}
int answer(){
vl v;
v.clear();
ll s = 1;
bool met = false;
for (int it : p){
if (s >= mod)
break;
int i = -it;
s *= x[i];
v.pb(i);
if (i == 0)
met = true;
}
sort(all(v));
reverse(all(v));
ll temp = s;
int sz = v.size();
ll mx = 0, yy = 0;
s = 1;
for (int i = sz - 2; i >= 0; i--){
s *= x[v[i]];
if (i)
yy = get_m(1, 1, n, v[i], v[i - 1] - 1);
else
yy = get_m(1, 1, n, v[i], n);
mx = max(mx, s * yy);
}
if (v[sz - 1] == 0){
yy = get_m(1, 1, n, 1, n);
return max(mx, yy) % mod;
}
else {
if (temp < mod && met == true)
assert(false);
if (sz > 1)
yy = get_m(1, 1, n, v[sz - 1], v[sz - 2] - 1);
else
yy = get_m(1, 1, n, v[sz - 1], n);
return (max(mx, yy) % mod * get(1, 1, n, 1, v[sz - 1])) % mod;
}
}
int init(int N, int X[], int Y[]){
n = N;
p.insert(0);
x[0] = 1LL;
y[0] = 1LL;
for (int i = 1; i <= n; i++){
x[i] = X[i - 1];
y[i] = Y[i - 1];
if (x[i] != 1)
p.insert(-i);
}
build(1, 1, n);
return answer();
}
int updateX(int pos, int val) {
pos++;
// if (!pos)
// assert(false);
if (x[pos] != 1 && val == 1)
p.erase(pos);
else if (x[pos] == 1 && val != 1)
p.insert(pos);
upd(1, 1, n, pos, 1LL * val);
x[pos] = 1LL * val;
return answer();
}
int updateY(int pos, int val) {
pos++;
y[pos] = 1LL * val;
upd_m(1, 1, n, pos, 1LL * val);
return answer();
}
