#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 500000;
const int MOD = 1000000007;
template<typename T, typename Upd>
struct Aint {
T aint[1+4*MAX_N];
T neutralQry, initVal;
Upd upd;
Aint(T nq, T iv) {
neutralQry = nq;
initVal = iv;
for(int i = 0; i <= 4*MAX_N; ++i)
aint[i] = initVal;
}
void update(int poz, T val, int l = 1, int r = MAX_N, int nod = 1) {
if(poz < l || r < poz) return;
if(l == r)
aint[nod] = upd.update(aint[nod], val);
else {
int mid = (l + r) / 2;
update(poz, val, l, mid, 2 * nod);
update(poz, val, mid + 1, r, 2 * nod + 1);
aint[nod] = upd.query(aint[2 * nod], aint[2 * nod + 1]);
}
}
T query(int i, int j, int l = 1, int r = MAX_N, int nod = 1) {
if(j < l || r < i) return neutralQry;
if(i <= l && r <= j) return aint[nod];
else {
int mid = (l + r) / 2;
return upd.query(query(i, j, l, mid, 2 * nod),
query(i, j, mid + 1, r, 2 * nod + 1));
}
}
};
struct Upd1 {
int update(int a, int b) { return b; }
int query(int a, int b) { return max(a, b); }
};
struct Upd2 {
int update(int a, int b) { return b; }
int query(int a, int b) { return (long long)a * b % MOD;}
};
int N;
int x[1+MAX_N], y[1+MAX_N];
set<int> rel;
Aint<int, Upd1> maxaint(-1, -1), prodaint(1, 1);
int getResult() {
int k = 0;
long long best, rez, prod;
best = rez = 0;
set<int>::reverse_iterator it = rel.rbegin();
set<int>::iterator it2;
prod = 1;
while(it != rel.rend() && prod <= 1000000000) {
prod = prod * x[*it];
it++;
}
prod = 1;
it2 = it.base();
while(it2 != rel.end()) {
int pos = *it2, maxy;
prod = prod * x[pos];
maxy = maxaint.query(pos, N);
if(prod * maxy > best) {
best = prod * maxy;
rez = prod * maxy % MOD * prodaint.query(1, pos - 1) % MOD;
}
it2++;
}
return rez;
}
int init(int n, int _x[], int _y[]) {
N = n;
rel.insert(0);
x[0] = y[0] = 1;
for(int i = 1; i <= n; ++i) {
x[i] = _x[i - 1];
y[i] = _y[i - 1];
if(x[i] != 1)
rel.insert(i);
maxaint.update(i, y[i]);
prodaint.update(i, x[i]);
}
return getResult();
}
int updateX(int pos, int val) {
pos++;
rel.erase(pos);
x[pos] = val;
if(val != 1)
rel.insert(pos);
prodaint.update(pos, val);
return getResult();
}
int updateY(int pos, int val) {
pos++;
y[pos] = val;
maxaint.update(pos, val);
return getResult();
}
