#include "horses.h"
#include <bits/stdc++.h>
#define ll long long
#define s second
#define f first
#define pb push_back
#define left (h<<1),l,(l+r)>>1
#define right ((h<<1)|1),((l+r)>>1) + 1,r
using namespace std;
const int mod = 1000000007,N = 500005;
ll x[N],y[N],ans;
int n;
struct {
ll nam;
ll maxy;
int id;
//id = (l,r) shualedshi 1sgan(x[i]) gansxvavebuli sul marjvena ricxvis indexi
} t[4*N];
void upd(int h,int l,int r,int idx){
if (l == r){
t[h].id = 0;
if (x[l] != 1) t[h].id = l;
t[h].nam = x[l];
t[h].maxy = y[l];
return;
}
if (idx > (l + r)/2) upd(right,idx);
else upd(left,idx);
if (x[t[h*2 + 1].id] > 1){
t[h].id = t[h*2 + 1].id;
}else if (x[t[h*2].id] > 1){
t[h].id =t[h*2].id;
}else{
t[h].id=0;
}
t[h].maxy = max(t[h*2].maxy, t[h*2+1].maxy);
t[h].nam = (t[h*2].nam * t[h*2+1].nam)%mod;
}
ll getnam (int h,int l,int r,int L,int R){
if (r < L || R < l) return 1;
if (L <= l && r <= R) return t[h].nam;
ll X = getnam(left,L,R),Y = getnam(right,L,R);
return (X*Y)%mod;
}
ll getid(int h,int l,int r,int L,int R){
if (r < L || R < l) return 0LL;
if (L <= l && r <= R) return t[h].id;
int X = getid(left,L,R),Y = getid(right,L,R);
if (x[Y] > 1) return Y;
if (x[X] > 1) return X;
return 0;
}
ll getmaxy(int h,int l,int r,int L,int R){
if (r < L || R < l) return 0LL;
if (L <= l && r <= R) return t[h].maxy;
return max(getmaxy(left,L,R),getmaxy(right,L,R));
}
void go(){
vector <pair<ll,ll>> vec; vec.clear();
int r = n;
for (int o = 1; o <= 60; o++){
if (r < 1) break;
if (x[r] != 1LL) {
vec.pb({x[r],y[r]});
r--;
continue;
}
int res = getid(1,1,n,1,r) + 1;
vec.pb({1LL,getmaxy(1,1,n,res,r)});
r = res - 1;
}
reverse(vec.begin(),vec.end());
ll k = 1LL,yy = vec[0].s,p = vec[0].f;
bool q=0;
ans = (p*yy)%mod;
for (int j = 1; j<vec.size(); j++){
ll X = vec[j].f,Y = vec[j].s;
p = (p * X)%mod;
if (!q && k < 1e9) k *= X;
if (k >= 1e9) q=1;
if (q || (k*Y >= yy)){
yy = Y;
ans = (p * Y)%mod;
k=1LL; q=0;
}
}
ans = (ans * getnam(1,1,n,1,r))%mod;
}
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],upd(1,1,n,i);
go();
return ans;
}
int updateX(int pos, int val) {
pos++;
x[pos] = val;
upd(1,1,n,pos);
go();
return ans;
}
int updateY(int pos, int val) {
pos++;
y[pos]=val;
upd(1,1,n,pos);
go();
return ans;
}
