#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=5e5+7;
const ll MOD=1e9+7;
set<pair<ll,ll>>S;
ll ilo[4*LIM], ilomod[4*LIM], tr[4*LIM], N=1, n;
ll cntilo(int l, int r) {
l+=N; r+=N;
ll ans=ilo[l];
if(l!=r) ans=min(ans*ilo[r], MOD);
while(l/2!=r/2) {
if(l%2==0) ans=min(ans*ilo[l+1], MOD);
if(r%2==1) ans=min(ans*ilo[r-1], MOD);
l/=2; r/=2;
}
return ans;
}
ll cntma(int l, int r) {
l+=N; r+=N;
ll ans=max(tr[l], tr[r]);
while(l/2!=r/2) {
if(l%2==0) ans=max(ans, tr[l+1]);
if(r%2==1) ans=max(ans, tr[r-1]);
l/=2; r/=2;
}
return ans;
}
ll cntmod(int l, int r) {
if(r<l) return 1;
l+=N; r+=N;
ll ans=ilomod[l];
if(l!=r) ans=(ans*ilomod[r])%MOD;
while(l/2!=r/2) {
if(l%2==0) ans=(ans*ilomod[l+1])%MOD;
if(r%2==1) ans=(ans*ilomod[r-1])%MOD;
l/=2; r/=2;
}
return ans;
}
ll solve() {
int p=0, k=n-1;
while(p<k) {
int sr=(p+k)/2;
if(cntilo(sr, n-1)==MOD) p=sr+1; else k=sr;
}
ll ans=0, akt=1;
if(k) ans=tr[N+k-1];
//if(n-k>50) return MOD;
while(k<n) {
akt*=ilo[k+N];
auto it=S.upper_bound({k, -MOD});
auto a=*it;
if(a.st>k+1) a={k, k};
else a={k, a.nd};
ans=max(ans, akt*cntma(a.st, a.nd));
k=a.nd+1;
}
ans%=MOD;
ans=(ans*cntmod(0, p-1))%MOD;
return ans;
}
int init(int D, int X[], int Y[]) {
n=D;
while(N<n) N*=2;
rep(i, 2*N) ilo[i]=ilomod[i]=1;
rep(i, n) {
ilo[N+i]=ilomod[N+i]=X[i];
tr[N+i]=Y[i];
}
for(int i=N-1; i; --i) {
ilo[i]=min(ilo[2*i]*ilo[2*i+1], MOD);
ilomod[i]=(ilomod[2*i]*ilomod[2*i+1])%MOD;
tr[i]=max(tr[2*i], tr[2*i+1]);
}
S.insert({-MOD, -MOD});
S.insert({MOD, MOD});
/*int p=0;
rep(i, n) {
if(X[i]!=1) {
if(p!=i) S.insert({p, i-1});
p=i+1;
}
}
if(p!=n) S.insert({p, n-1});*/
return solve();
}
int updateX(int v, int x) {
/*if(ilo[v+N]==1) {
auto it=S.upper_bound({v, MOD+1}); --it;
auto p=*it;
if(p.nd==v) {
S.erase(it);
if(p.st!=p.nd) S.insert({p.st, p.nd-1});
} else if(p.st==v) {
S.erase(it);
S.insert({p.st+1, p.nd});
} else {
S.erase(it);
S.insert({p.st, v-1});
S.insert({v+1, p.nd});
}
}
if(x==1) {
auto it=S.upper_bound({v, v});
auto it2=it; --it2;
auto a=*it2, b=*it;
if(a.nd==v-1 && b.st==v+1) {
S.erase(it2);
it=S.upper_bound({v, v});
S.erase(it);
S.insert({a.st, b.nd});
} else if(a.nd==v-1) {
S.erase(it2);
S.insert({a.st, v});
} else if(b.st==v+1) {
S.erase(it);
S.insert({v, b.st});
} else S.insert({v, v});
}*/
v+=N;
ilo[v]=ilomod[v]=x;
v/=2;
while(v) {
ilo[v]=min(ilo[2*v]*ilo[2*v+1], MOD);
ilomod[v]=(ilomod[2*v]*ilomod[2*v+1])%MOD;
v/=2;
}
return solve();
}
int updateY(int v, int x) {
v+=N;
tr[v]=x;
v/=2;
while(v) {
tr[v]=max(tr[2*v], tr[2*v+1]);
v/=2;
}
return solve();
}
