#include "horses.h"
#include <set>
#include <vector>
#include <iostream>
#define ll long long
using namespace std;
const int mod = 1000000007;
int N;
ll X [5000000];
ll Y [5000000];
ll seg [5000000];//max segtree
ll lc [5000000];//max segtree
ll rc [5000000];//max segtree
set <int, greater<int>> pos;
ll prod = 1;
int cnod = 5;
int root;
ll fpow(ll a, ll b){
if(b == 0){
return 1;
}else{
ll half = fpow(a, b/2);
half = (half * half)%mod;
if(b%2 == 1){
half = (half * a)%mod;
}
return half;
}
}
ll inv(ll a){
return fpow(a, mod-2);
}
int nnod(){
return cnod++;
}
int build(int cur, int l, int r){
if(l == r){
seg[cur] = Y[l];
}else{
lc[cur] = nnod();
rc[cur] = nnod();
build(lc[cur], l, (l+r)/2);
build(rc[cur], (l+r)/2+1, r);
seg[cur] = max(seg[lc[cur]], seg[rc[cur]]);
}
return cur;
}
void change(int cur, int l, int r, int x, int v){
if(l <= x && x <= r){
if(l == r){
Y[x] = v;
seg[cur] = v;
}else{
change(lc[cur], l, (l+r)/2, x, v);
change(rc[cur], (l+r)/2+1, r, x, v);
seg[cur] = max(seg[lc[cur]], seg[rc[cur]]);
}
}
}
ll getMax(int cur, int l, int r, int fl, int fr){
if(fl <= l && r <= fr){
return seg[cur];
}else if(r < fl || fr < l){
return 0;
}else{
return max(getMax(lc[cur], l, (l+r)/2, fl, fr), getMax(rc[cur], (l+r)/2+1, r, fl, fr));
}
}
int query(){
auto it = (pos.begin());
vector <pair<ll, ll>> mva;
ll div = 1;
ll prv = N-1;
while(true){
int x = *(it);
// cerr << "?" << x << endl;
mva.push_back(make_pair(getMax(root, 0, N-1, max(0, x), prv), div));
prv = x-1;
if(x == -1){
break;
}
if(div * X[x] > 1000000000ll){
break;
}
div *= X[x];
it = next(it);
}
// cerr << "DONE" << endl;
ll ans = 0;
for(int i = 0; i < mva.size(); i++){
ans = max(ans, mva[i].first * div/mva[i].second);
}
ans = ans%mod;
cerr << ans << endl;
return (int)(((prod * ans)%mod * inv(div))%mod);
}
int init(int N_, int X_[], int Y_[]) {
N = N_;
for(int i = 0; i < N; i++){
X[i] = X_[i];
Y[i] = Y_[i];
}
pos.insert(-1);
for(int i = 0; i < N; i++){
if(X[i] > 1){
//cerr << X[i] << " " << i << " ";
pos.insert(i);
prod = (prod * X[i])%mod;
}
}
// cerr << endl;
root = build(nnod(), 0, N-1);
// cerr << "INIT DONE" << endl;
/*for(auto a : pos){
cerr << (a) << " ";
}
cerr << endl;*/
return query();
}
int updateX(int p, int v) {
pos.erase(p);
prod = (prod * inv(X[p]))%mod;
X[p] = v;
if(v != 1){
pos.insert(p);
}
prod = (prod * v)%mod;
return query();
}
int updateY(int p, int v) {
change(root, 0, N-1, p, v);
return query();
}
