#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int N, *X, *Y_;
set<pii> S;
const ll MAX=1e9+7;
ll mypow(int n)
{
int i=30;
ll ret=1;
for (; i>=0; i--) {
ret=ret*ret%MAX;
if ((1<<i)&(MAX-2)) ret=ret*n%MAX;
}
return ret;
}
ll mul=1;
struct seg{
vector<int> Y;
int initF(int ind, int i, int dx, int dy) {
if (dx>dy||ind<dx||dy<ind) return Y[i];
if (dx==dy&&dx==ind) {
Y[i]=Y_[ind];
return Y[i];
}
int ret=0, md=(dx+dy)/2;
ret=max(ret, initF(ind, i*2, dx, md));
ret=max(ret, initF(ind, i*2+1, md+1,dy));
Y[i]=ret;
return Y[i];
}
void init() {
Y.resize(N*3);
for (int i=0; i<N; i++) initF(i, 1, 0, N-1);
}
int mx(int s, int e, int i, int dx, int dy) {
if (dx>dy||dy<s||e<dx) return 0;
if (s<=dx&&dy<=e) return Y[i];
if (dx==dy) return 0;
int md=(dx+dy)/2;
int mx1=mx(s,e,i*2,dx,md), mx2=mx(s,e,i*2+1,md+1,dy);
return max(mx1, mx2);
}
}Seg;
ll getAns()
{
//puts("OK getANS");
set<pii, greater<pii> >::iterator it;
ll now=1, ymx;
ll mx1=0, mx2=1;
ll ret=1;
it=S.end();
for (; it-- != S.begin(); ) {
ymx=Seg.mx((*it).first, (*it).second, 1, 0, N-1);
//printf("%d %d ", (*it).first, (*it).second);
if (mx1*now<ymx*mx2) {
ret=mul*mypow((int)now)%MAX;
ret=ret*ymx%MAX;
mx1=ymx; mx2=now;
}
//printf("%lld %lld %lld\n", now, ret, ymx);
now*=X[(*it).first];
if (now>(1ll<<30)) break;
}
//printf("%lld\n", ret);
return ret;
}
int init(int N_, int x[], int y[]) {
X=x, Y_=y;
N=N_;
for (int i=0; i<N; i++) mul=mul*x[i]%MAX;
Seg.init();
for (int i=N-1; i>=0; i--) {
int j;
for (j=i; j; j--) {if (x[j]!=1) break;}
S.insert({j,i});
i=j;
if (i<0) assert(false);
}
//for (auto it=S.begin(); it!=S.end(); ++it) printf("{%d, %d} ", (*it).first, (*it).second);
return (int)getAns();
}
int updateX(int pos, int val) {
//puts("OK X");
mul=mul*mypow(X[pos])%MAX; mul=mul*val%MAX;
set<pii, greater<pii> >::iterator it, it1;
if (X[pos]==1&&val!=1) {
it=S.lower_bound({pos,0});
if (it!=S.begin()){
it--;
//printf("A; %d %d\n", (*it).first, (*it).second);
if ((*it).first<pos&&pos<=(*it).second) {
pii pi;
pi=(*it);
S.erase(it);
S.insert({pi.first, pos-1}); S.insert({pos, pi.second});
}
else assert(false);
}
}
else if (X[pos]!=1&&val==1) {
it=S.lower_bound({pos,0});
//printf("B; %d %d\n", (*it).first, (*it).second);
it1=it;
if (it!=S.begin()) {
it1--;
pii pi={(*it1).first, (*it).second};
pii pi1=(*it1), pi2=(*it);
if ((*it).first==pos) {
S.erase(pi1); S.erase(pi2);
S.insert(pi);
}
else assert(false);
}
}
X[pos]=val;
return (int)getAns();
}
int updateY(int pos, int val) {
//puts("OK Y");
Y_[pos]=val;
Seg.initF(pos, 1, 0, N-1);
return (int)getAns();
}
