#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define Tree int h,int l,int r
#define left 2*h,l,(l+r)/2
#define right 2*h+1,(l+r)/2+1,r
#define Pb push_back
#define F first
#define S second
int Inf=1000000008,Mod=1000000007;
int P,n,x[500002],y[500002],ANS;
int Ind,Z;
int v[3000002];
pair < int , int > vy[3000002];
set < int > st;
set < int > :: iterator it;
vector < int > V;
pair < int , int > K;
int L,R;
void Update(Tree)
{
if (l>L || r<L) return ;
if (L==l && r==L) { v[h]=R%Mod; return ; }
Update(left);
Update(right);
v[h]=(1LL*v[2*h]*v[2*h+1])%Mod;
}
int Get(Tree)
{
if (L>r || l>R) return 1;
if (L<=l && r<=R) return v[h];
return (1LL*Get(left)*Get(right))%Mod;
}
void Upy(Tree)
{
if (l>L || r<L) return ;
if (L==l && r==L) { vy[h].F=R; vy[h].S=L; return ; }
Upy(left);
Upy(right);
if (vy[2*h].F>vy[2*h+1].F) vy[h]=vy[2*h];
else vy[h]=vy[2*h+1];
}
pair < int , int > Gety(Tree)
{
if (L>r || l>R) return make_pair(0,0);
if (L<=l && r<=R) return make_pair(vy[h].F,vy[h].S);
pair < int , int > X1=Gety(left);
pair < int , int > X2=Gety(right);
if (X1.F>X2.F) return X1;
return X2;
}
int init(int N, int X[], int Y[]) {
n=N;
for (int i=1; i<=n; i++)
x[i]=X[i-1],y[i]=Y[i-1];
for (int i=1; i<=n; i++)
{
L=i; R=x[i];
Update(1,1,n);
if (x[i]>1) st.insert(i);
}
for (int i=1; i<=n; i++)
{
L=i; R=y[i];
Upy(1,1,n);
}
Ind=1;
P=1;
for (int j=2; j<=n; j++)
{
if (1LL*P*x[j]<Inf) P*=x[j];
else P=Inf;
if (y[Ind]<1LL*P*y[j]) P=1,Ind=j;
}
L=1; R=Ind;
ANS=(1LL*Get(1,1,n)*y[Ind])%Mod;
return ANS;
}
int Ann()
{
it=st.end();
V.clear();
Z=0;
while (it!=st.begin())
{
Z++;
it--;
V.Pb((*it));
if (Z>35) break;
}
if (!V.size() || V[V.size()-1]!=1) V.Pb(1);
reverse(V.begin(),V.end());
if (!V.size() || V[V.size()-1]!=n) V.Pb(n);
Ind=1;
P=1;
for (int i=0; i<V.size(); i++)
{
if (1LL*P*x[V[i]]<Inf) P*=x[V[i]];
else P=Inf;
if (y[Ind]<1LL*P*y[V[i]]) P=1,Ind=V[i];
if (i==V.size()-1) continue;
L=V[i]+1; R=V[i+1]-1;
K=Gety(1,1,n);
if (y[Ind]<1LL*P*K.F) P=1,Ind=K.S;
}
L=1; R=Ind;
ANS=(1LL*Get(1,1,n)*y[Ind])%Mod;
return ANS;
}
int updateX(int pos, int val) {
pos++;
L=pos; R=val;
if (x[pos]==1 && val>1) st.insert(pos);
else
if (x[pos]>1 && val==1) st.erase(st.find(pos));
x[pos]=val;
Update(1,1,n);
return Ann();
}
int updateY(int pos, int val) {
pos++;
L=pos; R=val;
y[pos]=val;
Upy(1,1,n);
return Ann();
}
