// #ifdef __AVX2__
// #pragma GCC target "avx2"
// #endif
// #pragma GCC optimize "O3"
// #pragma GCC optimize "unroll-loops"
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
// #define int long long
#define elif else if
#define all(l) begin(l),end(l)
#define rall(l) rbegin(l),rend(l)
#define append push_back
#define print(l) for(auto i:l) cout<<i<<' '; cout<<endl;
#define pprint(a,b) cout<<a<<' '<<b<<endl;
#define inp(l) for(auto &i:l) cin>>i;
// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define pai make_pair
#define endl "\n"
#define pii pair<int,int>
#define fi first
#define se second
#define vec vector
// const int mod=998244353;
const int mod1=998244353;
const int mod=1e9+7;
const int MA=5e5+5;
#define ll long long
ll n;
ll x[MA],y[MA];
struct node{
ll ma,mu1,li,ri;
node* ch[2];
node(){
ma=0;
mu1=1;
ch[0]=ch[1]=NULL;
}
void init(int l,int r){
li=l;
ri=r;
}
void set(int i,int v){
if(li==ri){
ma=mu1=v;
return;
}
int m=(li+ri)/2;
ma=0;
mu1=1;
if(i<=m){
if(ch[0]==NULL){
ch[0]=new node;
ch[0]->init(li,m);
}
ch[0]->set(i,v);
}
else{
if(ch[1]==NULL){
ch[1]=new node;
ch[1]->init(m+1,ri);
}
ch[1]->set(i,v);
}
if(ch[0]!=NULL){
ma=(*ch[0]).ma;
mu1=(*ch[0]).mu1;
}
if(ch[1]!=NULL){
ma=max(ma,(*ch[1]).ma);
mu1=(((*ch[1]).mu1)*mu1)%mod;
}
}
int mx(int l,int r){
if(l<=li and ri<=r) return ma;
int x=0;
int m=(li+ri)/2;
if(l<=m) x=ch[0]->mx(l,r);
if(r>m) x=max(x,ch[1]->mx(l,r));
return x;
}
ll mul(int l,int r){
if(r<li or l>ri) return 1;
if(l<=li and ri<=r) return mu1;
ll x=1;
int m=(li+ri)/2;
if(l<=m) x=ch[0]->mul(l,r);
if(r>m) x=(x*ch[1]->mul(l,r));
return x%mod;
}
};
node ry;
node rx;
set<pii>seg;
#define int1 __int128
int i1=-1;
int ans(){
deque<pii>a;
int1 tem=1;
while(tem<1e9){
pii b=*(seg.rbegin());
a.push_front(b);
seg.erase(b);
tem*=x[b.fi];
}
int1 intem=tem;
int1 ma=0,ans1=0;
if(a[0].fi==0){
tem/=x[0];
intem/=x[0];
if(tem<1e9){
ans1=ry.mx(1,n);
}
seg.insert(a[0]);
a.pop_front();
}
if(a.empty()){
return ry.mx(1,n);
}
tem=1;
for(int i=0;i<a.size();i++){
pii b=a[i];
tem*=x[b.fi];
ma=max(ma,tem*(int1)ry.mx(b.fi,b.se));
}
for(auto i:a){
seg.insert(i);
}
ma*=rx.mul(1,a[0].fi-1);
if(intem<1e9){
ma=max(ma,ans1);
}
ma%=mod;
return ma;
}
int updateX(int i,int v){
i++;
i1=i;
int pr=x[i];
x[i]=v;
rx.set(i,v);
if(pr>1 and v>1) return ans();
if(pr==v) return ans();
if(v==1){
auto p=seg.lower_bound(pai(i,0));
auto p1=p;
p1--;
pii a=*p,b=*p1;
seg.erase(a);
seg.erase(b);
seg.insert(pai(b.fi,a.se));
}
else{
auto p=seg.lower_bound(pai(i,0));
p--;
pii a=*p;
seg.erase(a);
seg.insert(pai(a.fi,i-1));
seg.insert(pai(i,a.se));
}
return ans();
}
int updateY(int i,int v){
i++;
ry.set(i,v);
y[i]=v;
return ans();
}
int init(int N,int X[],int Y[]){
n=N;
ry.init(0,n+5);
rx.init(0,n+5);
x[0]=1e9;
for(int i=1;i<=n;i++){
x[i]=X[i-1];
rx.set(i,x[i]);
y[i]=Y[i-1];
ry.set(i,y[i]);
}
int l,r;
l=r=0;
for(int i=1;i<=n;i++){
if(x[i]>1){
seg.insert(pai(l,r));
l=r=i;
}
else
r++;
}
seg.insert(pai(l,r));
int1 tem=1;
return ans();
}
