#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll m = 1000000007;
ll mexp(ll a, ll b){
if (b==0){
return 1;
}
ll ans = mexp(a,b/2);
if (b%2==0){
return (ans*ans)%m;
} else {
return (((ans*ans)%m)*a)%m;
}
}
ll minv(ll x){
return mexp(x,m-2);
}
ll mdiv(ll a, ll b){
//a div b mod m
return (a*minv(b))%m;
}
//range maximum query
//4.14.20
struct Node{
int s,e,m,v;
Node *l, *r;
Node(int _s, int _e, int arr[]){
s=_s;e=_e;
if (s==e){
v=arr[s];
} else {
m=(s+e)/2;
l=new Node(s,m,arr);
r=new Node(m+1,e,arr);
v=max(l->v,r->v);
}
}
void update(int ind, int val){
if (s==e){
v=val;
return;
}
if (ind<=m){
l->update(ind,val);
} else {
r->update(ind,val);
}
v=max(l->v,r->v);
}
int query(int a, int b){
if (s==a&&e==b){
return v;
}
if (b<=m){
return l->query(a,b);
} else if (m<a){
return r->query(a,b);
} else {
return max(l->query(a,m),r->query(m+1,b));
}
}
};
//4.11.56
Node *root;
int n;
int *xvals;
int *yvals;
set<pair<int,int>> xset;
ll xprod = 1;
int query(){
auto it = prev(xset.end());
ll valdiv = 1; //value 'lost' from xvals suffix
ll maxfracn = 1;
ll maxfracd = 1;
while (true){
if (it->first==0){break;}
int mincrd = (it==xset.begin())?0:(prev(it)->first);
int maxcrd = it->first-1;
//cout<<mincrd<<' '<<maxcrd<<'\n';
int maxy = root->query(mincrd,maxcrd);
//cout<<maxy<<'\n';
valdiv*=it->second;
if (valdiv>m){
break;
}
ll newfracn = maxy;
ll newfracd = valdiv;
if (newfracn*maxfracd>maxfracn*newfracd){
maxfracn=newfracn;
maxfracd=newfracd;
}
if (it==xset.begin()){break;}
it = prev(it);
}
//cout<<"f "<<maxfracn<<' '<<maxfracd<<'\n';
return (((xprod*maxfracn)%m)*minv(maxfracd))%m;
}
int init(int N, int X[], int Y[]) {
n=N;
root = new Node(0,n-1,Y);
xvals=X;
yvals=Y;
for (int i = 0; i<n; i++){
xprod*=xvals[i];
xprod%=m;
if (xvals[i]!=1){
xset.insert({i,xvals[i]});
}
}
xset.insert({n,1});
return query();
}
int updateX(int pos, int val) {
if (xvals[pos]!=1){
xset.erase({pos,xvals[pos]});
}
xprod=mdiv(xprod,xvals[pos]);
xvals[pos]=val;
if (val!=1){
xset.insert({pos,xvals[pos]});
}
xprod*=xvals[pos];
xprod%=m;
return query();
}
int updateY(int pos, int val) {
yvals[pos]=val;
root->update(pos,val);
return query();
}
