#include"horses.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5;
const long long mod=1e9+7;
const long long INF=1e9;
int fen[MAXN],he[MAXN],seg[MAXN*4],n;
long long pref[MAXN];
long long poww(long long n,long long m)
{
long long res=n,ans=1;
while(m)
{
if(m&1) ans=ans*res%mod;
res=res*res%mod,m/=2;
}
return ans;
}
int getlog(long long n) { return 63-__builtin_clzll(n); }
void update(int i,int n,int val) { for(;i<=n;i+=i&-i) fen[i]+=val; }
int get(int i) { int ans=0;for(;i;i-=i&-i) ans+=fen[i];return ans; }
int walk(int n,int val)
{
if(val==0) return 0;
int ans=0;
for(int i=getlog(n);i+1;i--) if(ans+(1<<i)<=n&&val>fen[ans+(1<<i)]) val-=fen[ans+=(1<<i)];
return ans+1;
}
void updhe(int i,int n,long long val) { for(;i<=n;i+=i&-i) pref[i]=pref[i]*val%mod; }
long long gethe(int i) { long long ans=1;for(;i;i-=i&-i) ans=ans*pref[i]%mod;return ans; }
void update(int l,int r,int i,int val,int pos)
{
if(i<l||r<i) return ;
if(l==r)
{
seg[pos]=val;
return ;
}
int mid=(l+r)/2;
update(l,mid,i,val,pos*2);
update(mid+1,r,i,val,pos*2+1);
seg[pos]=max(seg[pos*2],seg[pos*2+1]);
}
int get(int l,int r,int u,int v,int pos)
{
if(u<=l&&r<=v) return seg[pos];
int mid=(l+r)/2;
if(v<=mid) return get(l,mid,u,v,pos*2);
if(mid+1<=u) return get(mid+1,r,u,v,pos*2+1);
return max(get(l,mid,u,v,pos*2),get(mid+1,r,u,v,pos*2+1));
}
int solve()
{
int k=get(n);
long long res=1,val=1,w=1,ans=0;
vector<int> vi;
vi.push_back(n+1);
for(int i=k;i+1;i--)
{
int pos=walk(n,i);
vi.push_back(max(1,pos));
if((res*=he[pos])>INF)
{
val=gethe(pos);
break;
}
}
reverse(vi.begin(),vi.end());
vi.erase(unique(vi.begin(),vi.end()),vi.end());
int sz=vi.size();
for(int i=0;i<sz-1;i++)
{
int l=vi[i],r=vi[i+1],mx=get(1,n,l,r-1,1);
w*=he[l],ans=max(ans,w*mx);
}
return ans%mod*val%mod;
}
void updatex(int pos,int val)
{
updhe(pos,n,poww(he[pos],mod-2)*val%mod);
update(pos,n,-(he[pos]>1)+(val>1));
he[pos]=val;
}
void updatey(int pos,int val)
{
update(1,n,pos,val,1);
}
int init(int N,int X[],int Y[])
{
n=N;
for(int i=0;i<=N;i++) he[i]=1;
for(int i=1;i<=N;i++)
{
updatex(i,X[i-1]);
updatey(i,Y[i-1]);
}
return solve();
}
int updateX(int pos,int val)
{
updatex(pos+1,val);
return solve();
}
int updateY(int pos,int val)
{
updatey(pos+1,val);
return solve();
}
