#include <bits/stdc++.h>
#include "horses.h"
#define ll long long
#define lp(i,a,b) for(int i=a;i<b;i++)
#define pii pair<int,int>
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
const int MOD = 1e9+7 ;
const int MAXN=5e5+10;
using namespace std ;
// ------------x------------
struct segOfMaximum
{
int v[MAXN*4];
int m(int l, int r){ return (l+r)/2 ; }
void upd(int pos, int l, int r, int x, int val)
{
if(l==r) { v[pos] = val; return ; }
if(x<=m(l,r)) upd(pos*2,l,m(l,r),x,val) ;
else upd(pos*2+1,m(l,r)+1, r, x, val) ;
v[pos] =max(v[pos*2], v[pos*2+1]);
}
int query(int pos, int l, int r, int beg, int en)
{
if(l>en || r<beg)return -1;
if(l>=beg && r<=en) return v[pos];
int rl = query(pos*2, l, m(l,r),beg,en) ;
int rr = query(pos*2+1,m(l,r)+1, r, beg, en) ;
return max(rl,rr) ;
}
void print(int pos, int l, int r)
{
printf("%d %d -> %d\n" , l ,r,v[pos]) ;
if(l==r)return ;
print(pos*2,l,m(l,r)) ;
print(pos*2+1, m(l,r)+1, r) ;
}
} ;
// ------------x------------
int n , x[MAXN] , y[MAXN] ;
set<pii> s ;
segOfMaximum cuteSeg ;
ll intervalFun(vector<pii> &v)
{
ll acumProd = 1 ;
ll myAns = 0 ;
int i = 0 , j = v.size() ;
for(int g = 1 ; g < j ; g++ )
{
acumProd *= v[g].ff ;
if(acumProd >= 1000000000)
acumProd/=v[++i].ff ;
}
acumProd=1 ;
for(int g = i; g < j ; g++ )
{
acumProd *= v[g].ff ;
myAns = max(myAns, acumProd*v[g].ss ) ;
}
lp(g,0,i) myAns = (myAns * v[g].ff)%MOD ;
return myAns ;
}
int ans()
{
int cont = 0 ;
set<pii>::iterator it= s.end() , it2 ;
while(cont<30 && it!=s.begin())
{
--it ;
if(it->ff == it->ss && x[it->ss]>1)
cont ++ ;
}
vector<pii> myVector ;
it2= it ;
while(it!=s.end())
{
myVector.pb( mk( x[it->ff] ,cuteSeg.query(1,0,n-1,it->ff, it->ss) ) ) ;
++it;
}
ll cool= intervalFun(myVector) ;
while(it2 != s.begin())
{
--it2 ;
cool *= x[it2->ff] ;
cool %= MOD;
}
return cool ;
}
int init(int N, int X[] ,int Y[])
{
n = N ;
lp(i,0,n) x[i] = X[i] , y[i]= Y[i] ;
lp(i,0,n)
{
int j = i ;
while(j<n && x[j] == 1 ) {j++;}
if(x[i] ==1) j-- ;
s.insert(mk(i,j)) ;
i = j ;
}
lp(i,0,n) cuteSeg.upd(1,0,n-1,i,y[i]) ;
return ans() ;
}
int updateY(int pos, int val)
{
cuteSeg.upd(1,0,n-1, pos,val) ;
return ans() ;
}
int updateX(int pos, int val)
{
set<pii>::iterator it ;
if(x[pos] > 1 && val == 1)
{
it = s.find(mk(pos,pos)) ;
int beg = pos , en = pos ;
if(it!=s.begin()) beg = (--it)->ff , ++it;
if(it!=s.end()) en = (++it)->ss , --it;
if(x[beg]>1) beg=pos ;
if(x[en]>1) en = pos ;
s.erase(it) ;
s.insert(mk(beg,en)) ;
}
else if(x[pos] == 1 && val > 1)
{
it= s.upper_bound( mk(pos,MOD) ) ;
--it;
int beg = it->ff , en = it->ss ;
s.erase(it) ;
if( pos != beg )
s.insert( mk( beg , pos-1 ) ) ;
if( pos != en )
s.insert(mk( pos+1, en )) ;
s.insert(mk(pos,pos)) ;
}
x[pos] = val ;
return ans() ;
}
