#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
const ll MOD = 1e9 + 7;
const int maxN = 500000;
const int siz = 1048576 / 2;
int N;
int x[maxN];
int y[maxN];
int segTree[siz * 2];
int segTree2[siz * 2];
set<int> s;
void st(int i, int v, int p, int lx, int rx){
if(rx - lx == 1){
segTree[p] = v;
return;
}
int m = (lx + rx) / 2;
if(i < m) st(i, v, 2 * p + 1, lx, m);
else st(i, v, 2 * p + 2, m, rx);
segTree[p] = max(segTree[2 * p + 1], segTree[2 * p + 2]);
}
int mx(int l, int r, int p, int lx, int rx){
if(lx >= l && rx <= r) return segTree[p];
else if(lx >= r || rx <= l) return 0;
int m = (lx + rx) / 2;
int m1 = mx(l, r, 2 * p + 1, lx, m);
int m2 = mx(l, r, 2 * p + 2, m, rx);
return max(m1, m2);
}
void st_x(int i, int v, int p, int lx, int rx){
if(rx - lx == 1){
segTree2[p] = v;
return;
}
int m = (lx + rx) / 2;
if(i < m) st_x(i, v, 2 * p + 1, lx, m);
else st_x(i, v, 2 * p + 2, m, rx);
ll left = segTree2[2 * p + 1];
ll right = segTree2[2 * p + 2];
segTree2[p] = (left * right) % MOD;
}
ll mult(int l, int r, int p, int lx, int rx){
if(lx >= l && rx <= r) return segTree2[p];
else if(lx >= r || rx <= l) return 1;
int m = (lx + rx) / 2;
ll m1 = mult(l, r, 2 * p + 1, lx, m);
ll m2 = mult(l, r, 2 * p + 2, m, rx);
return (m1 * m2) % MOD;
}
int ans(){
vector<int> ind;
ll best = 0;
ll optimaly = -1;
int r;
if(s.empty() == false){
auto it = s.end();
it--;
ll curr = 1;
bool included = 0;
int limit = 1000000000;
while(curr <= limit){
curr *= x[*it];
ind.push_back(*it);
if(curr > limit) continue;
if(*it == 0) included = 1;
if(it != s.begin()) it--;
else{
if(*it != 0) ind.push_back(0);
break;
}
}
reverse(ind.begin(), ind.end());
curr = 1;
if(included) curr = x[0];
ind.push_back(N);
for(int i = 1; i < (int)ind.size(); i++){
ll bestY = mx(ind[i - 1], ind[i], 0, 0, siz);
if(best < curr * bestY){
optimaly = bestY;
best = curr * bestY;
r = i;
}
curr *= x[ind[i]];
}
}else{
ind.push_back(N);
r = 0;
optimaly = mx(0, N, 0, 0, siz);
}
return (optimaly * mult(0, ind[r], 0, 0, siz)) % MOD;
}
int init(int n, int X[], int Y[]) {
N = n;
for(int i = 0; i < siz; i++){
segTree[i] = 0; segTree2[i] = 1;
}
for(int i = 0; i < N; i++){
x[i] = X[i]; y[i] = Y[i];
st(i, y[i], 0, 0, siz);
st_x(i, x[i], 0, 0, siz);
if(x[i] != 1) s.insert(i);
}
return ans();
}
int updateX(int pos, int val) {
st_x(pos, val, 0, 0, siz);
if(x[pos] != 1 && val == 1) s.erase(pos);
else if(x[pos] == 1 && val != 1) s.insert(pos);
x[pos] = val;
return ans();
}
int updateY(int pos, int val) {
st(pos, val, 0, 0, siz);
return ans();
}
