#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define M 1000000007LL
struct SEG1{
ll seg[1<<20];
SEG1(void){
for(int i=0;i<1<<20;i++)seg[i]=1;
}
void update(int a,ll x){
a+=(1<<19)-1;
seg[a]=x%M;
while(a>0){
a=(a-1)/2;
seg[a]=seg[a*2+1]*seg[a*2+2]%M;
}
}
ll query(int a,int b,int l=0,int r=(1<<19)-1,int k=0){
if(r<a||b<l)return 1;
if(a<=l&&r<=b)return seg[k];
return query(a,b,l,(l+r-1)/2,k*2+1)*query(a,b,(l+r+1)/2,r,k*2+2)%M;
}
}seg1;
struct SEG2{
ll seg[1<<20];
SEG2(void){
for(int i=0;i<1<<20;i++)seg[i]=0;
}
void update(int a,ll x){
a+=(1<<19)-1;
seg[a]=x;
while(a>0){
a=(a-1)/2;
seg[a]=max(seg[a*2+1],seg[a*2+2]);
}
}
ll query(int a,int b,int l=0,int r=(1<<19)-1,int k=0){
if(r<a||b<l)return 0;
if(a<=l&&r<=b)return seg[k];
return max(query(a,b,l,(l+r-1)/2,k*2+1),query(a,b,(l+r+1)/2,r,k*2+2));
}
}seg2;
ll n,x[500005],y[500005];
set<ll>p;
int solve(void){
auto it=p.find(n);
vector<ll>a,b,c;
int la=n;
ll s=1;
while(1){
it--;
int v=*it;
a.push_back(v);
b.push_back(s);
c.push_back(seg2.query(v,la-1));
if(it==p.begin()||s*x[v]>=1000000000)break;
s*=x[v];
la=v;
}
pair<ll,int>ma=make_pair(-1,-1);
for(int i=0;i<a.size();i++){
ma=max(ma,make_pair(s/b[i]*c[i],i));
}
return seg1.query(0,a[ma.second])*c[ma.second]%M;
}
int init(int N,int X[],int Y[]) {
n=N;
p.insert(n);
for(int i=0;i<n;i++){
x[i]=X[i];
seg1.update(i,x[i]);
if(i==0||x[i]>1)p.insert(i);
y[i]=Y[i];
seg2.update(i,y[i]);
}
return solve();
}
int updateX(int pos,int val) {
x[pos]=val;
seg1.update(pos,val);
if(x[pos]>1)p.insert(pos);
else if(pos!=0)p.erase(pos);
return solve();
}
int updateY(int pos, int val) {
y[pos]=val;
seg2.update(pos,val);
return solve();
}
