#include "horses.h"
#include <bits/stdc++.h>
#pragma GCC target("lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define sp << " " <<
using namespace std;
const int inf = 1e9+6;
const int LIM = 2e5+1,MOD = 1e9+7;
int mult(int x,int y) {
return ((x%MOD)*(y%MOD))%MOD;
}
int expo(int x,int y) {
if (!y) return 1;
int e = expo(x,y/2);
e = mult(e,e);
if (y&1) e= mult(e,x);
return e;
}
int divide(int x,int y) {
return mult(x,expo(y,MOD-2));
}
struct FT {
int n;
vi bit;
FT(){}
FT(int nn) {
n = nn;
bit.assign(n+1,1);
}
void upd(int p,int v,int old) {
int prd = divide(v,old);
put(p,prd);
}
void put(int p,int v) {
for (int i = p;i<=n;i+=i&-i) bit[i] = mult(bit[i],v);
}
int get(int p) {
int ans = 1;
for (int i = p;i>0;i-=i&-i) ans = mult(ans,bit[i]);
return ans;
}
} ft;
struct ST {
vi t;
ST(){}
ST(int nn) {
t.assign(4*nn+1,0);
}
void update(int node,int l,int r,int p,int v) {
if (l == r) {
t[node] = v;
return;
}
int m = (l+r) >> 1;
if (p <= m) update(2*node,l,m,p,v);
else update(2*node+1,m+1,r,p,v);
t[node] = max(t[2*node],t[2*node+1]);
}
int query(int node,int l,int r,int L,int R) {
if (l > R || r < L) return 0;
if (l >= L && r <= R) return t[node];
int m = (l+r) >> 1;
return max(query(2*node,l,m,L,R),query(2*node+1,m+1,r,L,R));
}
} st;
set<int> checker;
vi xx,yy;
int nn;
int calc() {
auto it = checker.end();
int prd = 1;
while (it != checker.begin()) {
it = prev(it);
prd*=xx[*it];
if (prd > inf) {
it = next(it);
break;
}
}
vector<pii> v;
prd = 1;
int ans = 0;
int mx = -1;
for (;it != checker.end();it = next(it)) {
prd *= xx[*it];
int mxv = st.query(1,1,nn,*it,nn);
if (prd*mxv > mx) {
mx = prd*mxv;
ans = mult(ft.get(*it),mxv);
}
}
return ans;
}
int32_t init(int32_t N, int32_t X[], int32_t Y[]) {
checker.insert(1);
nn = N;
xx.resize(N+1),yy.resize(N+1);
for (int i=1;i<=N;i++) xx[i] = X[i-1],yy[i] = Y[i-1];
ft = FT(N);
st = ST(N);
for (int i = 1;i<=N;i++) {
if (xx[i] > 1) checker.insert(i);
ft.upd(i,xx[i],1);
st.update(1,1,N,i,yy[i]);
}
return calc();
}
int32_t updateX(int32_t pos, int32_t val) {
pos++;
if (xx[pos] > 1) checker.erase(pos);
if (val > 1) checker.insert(pos);
checker.insert(1);
ft.upd(pos,val,xx[pos]);
xx[pos] = val;
return calc();
}
int32_t updateY(int32_t pos, int32_t val) {
pos++;
st.update(1,1,nn,pos,val);
yy[pos] = val;
return calc();
}
