#include "horses.h"
#include <bits/stdc++.h>

#define ll long long
using namespace std;

const ll inf=1e9;
const int mod=1e9+7;
const int MAX=5e5+10;

struct segtree{
	int t[4*MAX];
	bool mark[4*MAX];

	segtree(){
		memset(mark,0,sizeof(mark));
	}

	void update(int v,int tl,int tr,int pos,int x){
		if(tl==tr){
			t[v]=x;
			return;
		}
		int tm=(tl+tr)/2;
		if(pos<=tm)update(2*v,tl,tm,pos,x);
		else update(2*v+1,tm+1,tr,pos,x);
		mark[v]=(mark[2*v]|mark[2*v+1]);
		if(t[2*v]*1ll*t[2*v+1]>=mod){
			mark[v]=1;
		}
		t[v]=(t[2*v]*1ll*t[2*v+1])%mod;
	}

	pair<int,bool> mrg(pair<int,bool> a,pair<int,bool> b){
		pair<int,bool> res={a.first*1ll*b.first%mod,(a.second|b.second)};
		if(a.first*1ll*b.first>=mod){
			res.second=1;
		}
		return res;
	}

	pair<int,bool> get(int v,int tl,int tr,int l,int r){
		if(l>r||tl>r||l>tr)return {1,0};
		if(l<=tl&&tr<=r)return {t[v],mark[v]};
		int tm=(tl+tr)/2;
		return mrg(get(2*v,tl,tm,l,r),get(2*v+1,tm+1,tr,l,r));
	}
}tx;

struct segtreeMx{
	pair<int,int> t[MAX];

	pair<int,int> mrg(pair<int,int> a,pair<int,int> b){
		if(a.first>=b.first)return a;
		else return b;
	}

	void update(int v,int tl,int tr,int pos,int x){
		if(tl==tr){
			t[v]={x,tl};
			return;
		}
		int tm=(tl+tr)/2;
		if(pos<=tm)update(2*v,tl,tm,pos,x);
		else update(2*v+1,tm+1,tr,pos,x);
		t[v]=mrg(t[2*v],t[2*v+1]);
	}

	pair<int,int> get(int v,int tl,int tr,int l,int r){
		if(l>r||tl>r||l>tr)return {0,0};
		if(l<=tl&&tr<=r)return t[v];
		int tm=(tl+tr)/2;
		return mrg(get(2*v,tl,tm,l,r),get(2*v+1,tm+1,tr,l,r));
	}
}ty;

int n;
set<int> st;
int x[MAX];
int y[MAX];

int get(int pos){
	return tx.get(1,1,n,1,pos).first*1ll*y[pos]%mod;
}

int get(){
	if(st.empty())return ty.get(1,1,n,1,n).first;
	bool f=0;
	if(!st.count(1)){
		st.insert(1);
		f=1;
	}
	vector<int> vec;
	int pos=ty.get(1,1,n,*st.rbegin(),n).second;
	vec.push_back(*st.rbegin());
	st.erase(--st.end());
	while(!st.empty()&&vec.size()<=40){
		// assert(*st.rbegin()==vec.back()-1);
		int pos1=ty.get(1,1,n,*st.rbegin(),vec.back()-1).second;
		vec.push_back(*st.rbegin());
		st.erase(--st.end());
		pair<int,bool> bf=tx.get(1,1,n,pos1+1,pos);
		if(bf.second||bf.first*1ll*y[pos]>=mod)break;
		if(bf.first*y[pos]<=y[pos1])pos=pos1;
	}
	for(int x:vec)st.insert(x);
	if(f){
		st.erase(1);
	}
	return get(pos);
}

int init(int N, int X[], int Y[]) {
	n=N;
	for(int i=0;i<N;i++){
		y[i+1]=Y[i];
		x[i+1]=X[i];
		tx.update(1,1,N,i+1,X[i]);
		ty.update(1,1,N,i+1,Y[i]);
		if(X[i]!=1){
			st.insert(i+1);
		}
	}
	return get();
}

int updateX(int pos, int val) {	
	pos++;
	if(x[pos]!=1)st.erase(pos);
	x[pos]=val;
	tx.update(1,1,n,pos,val);
	if(x[pos]!=1)st.insert(pos);
	return get();
}

int updateY(int pos, int val) {
	pos++;
	y[pos]=val;
	ty.update(1,1,n,pos,val);
	return get();
}