#include "horses.h"
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
class Segment_Tree{
private:
int n;
vl date;
public:
void Init(int n_){
n=1;
while(n<n_) n*=2;
date=vl(2*n-1,1);
}
void Update(int k,int x){
k+=n-1;
date[k]=x;
while(k>0){
k=(k-1)/2;
date[k]=date[k*2+1]*date[k*2+2]%mod;
}
}
ll Query(int a,int b){
a+=n-1;b+=n-1;
ll m=1;
while(a<b){
if(a%2==0) (m*=date[a++])%=mod;
if(b%2==0) (m*=date[--b])%=mod;
a/=2;b/=2;
}
return m;
}
ll Open(int k){return date[k+n-1];}
};
template <class T>
class RMQ{
private:
int n;
vector<T> rmq;
T dfs(int a,int b,int k,int l,int r){
if(r<=a||b<=l) return 0;
if(a<=l&&r<=b) return rmq[k];
int m=(l+r)/2;
return max(dfs(a,b,k*2+1,l,m),dfs(a,b,k*2+2,m,r));
}
public:
void Init(int n_){
n=1;
while(n<n_) n*=2;
rmq=vector<T>(2*n-1);
}
void Update(int k,T x){
k+=n-1;
rmq[k]=x;
while(k>0){
k=(k-1)/2;
rmq[k]=max(rmq[k*2+1],rmq[k*2+2]);
}
}
T Query(int a,int b){
return dfs(a,b,0,0,n);
}
};
int n;
set<int> st;
RMQ<int> rmq;
Segment_Tree seg;
vi a,b;
int f(){
ll t=1;
int id=n;
vi c;
while(t<=1000000000){
auto it=st.lower_bound(id);
if(it==st.begin()) break;
it--;
id=*it;
c.push_back(id);
t*=a[id];
// cout<<id<<' '<<a[id]<<' '<<t<<endl;
}
if(c.empty()) return rmq.Query(0,n);
reverse(c.begin(),c.end());
int m=(int)c.size();
t=1;
ll mx=0;
for(int i=0;i<m;i++){
if(i) t*=a[c[i]];
ll y=rmq.Query(c[i],(i==m-1?n:c[i+1]));
// cout<<t<<' '<<y<<' '<<c[i]<<' '<<(i==m-1?n:c[i+1])<<endl;
mx=max(mx,t*y);
}
mx%=mod;
return (int)(mx*seg.Query(0,c[0]+1)%mod);
}
int init(int N, int X[], int Y[]) {
n=N;
a=b=vi(n);
rmq.Init(N);
seg.Init(N);
for(int i=0;i<n;i++){
a[i]=X[i],b[i]=Y[i];
if(a[i]>1) st.insert(i);
seg.Update(i,a[i]);
rmq.Update(i,b[i]);
}
return f();
}
int updateX(int pos, int val){
if(a[pos]>1) st.erase(pos);
a[pos]=val;
if(a[pos]>1) st.insert(pos);
seg.Update(pos,val);
return f();
}
int updateY(int pos, int val) {
b[pos]=val;
rmq.Update(pos,val);
return f();
}
