#include <stdio.h>
#include <set>
using namespace std;
#define mp make_pair
#define ll long long
const int mod=1e9+7;
const int N=500050;
struct SegmentTreeProduct
{
int pro[1<<20];
SegmentTreeProduct(){ for(int i=0;i<(1<<20);i++) pro[i]=1;}
void Set(int i, int val){ i+=1<<19;pro[i]=val;for(i>>=1;i;i>>=1) pro[i]=(ll)pro[i<<1]*pro[i<<1|1]%mod;}
int Get(int l, int r)
{
int ret=1;
for(l+=1<<19,r+=1<<19;l<=r;l>>=1,r>>=1)
{
if(l%2==1) ret=(ll)ret*pro[l++]%mod;
if(r%2==0) ret=(ll)ret*pro[r--]%mod;
}
return ret;
}
} PTree;
int max(int a, int b){ return a>b?a:b;}
struct SegmentTreeMax
{
int rmq[1<<20];
SegmentTreeMax(){ for(int i=0;i<(1<<20);i++) rmq[i]=0;}
void Set(int i, int val){ i+=1<<19;rmq[i]=val;for(i>>=1;i;i>>=1) rmq[i]=max(rmq[i<<1],rmq[i<<1|1]);}
int Get(int l, int r)
{
int ret=0;
for(l+=1<<19,r+=1<<19;l<=r;l>>=1,r>>=1)
{
if(l%2==1) ret=max(ret,rmq[l++]);
if(r%2==0) ret=max(ret,rmq[r--]);
}
return ret;
}
} MTree;
set<pair<int,int> > Set;
set<pair<int,int> >::iterator it,it1;
void Cut(int i)
{
it=Set.lower_bound(mp(i,N));
if(it==Set.begin()) return;
it--;
int l=it->first,r=it->second;
if(r<i) return;
if(l<i)
{
Set.erase(mp(l,r));
Set.insert(mp(l,i-1));
Set.insert(mp(i,r));
}
}
void Split(int i){ Cut(i);Cut(i+1);}
int x[N],y[N],n;
int Solve()
{
it=Set.end();ll p=1;int sol=(ll)PTree.Get(1,n)*y[n]%mod;
while(it!=Set.begin())
{
it--;
int b=MTree.Get(it->first,it->second);
if(p<b) p=b,sol=(ll)PTree.Get(1,it->second)*b%mod;
p*=x[it->first];
if(p>mod) break;
}
return sol;
}
int init(int N, int X[], int Y[])
{
int i,j;n=N;
for(i=1;i<=n;i++) x[i]=X[i-1],y[i]=Y[i-1];
for(i=1;i<=n;i++) PTree.Set(i,x[i]),MTree.Set(i,y[i]);
for(i=1;i<=n;i++)
{
if(x[i]>1) Set.insert(mp(i,i));
else if(x[i-1]!=1)
{
for(j=i+1;j<=n && x[j]==1;j++);
Set.insert(mp(i,j-1));
}
}
return Solve();
}
int updateX(int p, int v)
{
p++;
if(x[p]==1 && v==1) return Solve();
if(x[p]==1) Split(p);
if(v==1)
{
if(x[p-1]==1)
{
it=Set.lower_bound(mp(p,p));
it1=it;it1--;
int l=it1->first,r=it->second;
Set.erase(it1);
Set.erase(it);
Set.insert(mp(l,r));
}
if(x[p+1]==1)
{
it=Set.lower_bound(mp(p,N));
it1=it;it1--;
int l=it1->first,r=it->second;
Set.erase(it1);
Set.erase(it);
Set.insert(mp(l,r));
}
}
PTree.Set(p,v);
x[p]=v;
return Solve();
}
int updateY(int p, int v)
{
p++;
MTree.Set(p,v),y[p]=v;
return Solve();
}
