#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(), x.end()
#define pi pair<int,int>
#define f first
#define s second
const int mod = 1e9+7;
#define int long long
int pw(int a, int b) {
int r=1;
while (b) {
if (b&1) r=(r*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return r;
}
int inv(int x) {
return pw(x,mod-2);
}
struct BIT {
vector<int> t; int n;
BIT(int n) {
this->n=n;
t.assign(n,1);
}
void add(int i, int x) {
for(;i<n;i=i|(i+1)) t[i]=(t[i]*x)%mod;
}
int sum(int r) {
int q=1;
for(;r>=0;r=(r&(r+1))-1) q=(q*t[r])%mod;
return q;
}
};
#undef int
int a[(int)5e5+5];
int c[(int)5e5+5];
BIT ft(5e5+5);
set<int> s;
int n;
struct sgt {
vector<int> t; int sz=1;
sgt(int n) {
while (sz<n) sz<<=1;
t.assign(2*sz,0);
}
int query(int v, int l, int r, int lx, int rx) {
if (rx<=l || r<=lx) return 0;
if (lx<=l && r<=rx) return t[v];
int m=(l+r)>>1;
int lq=query(2*v+1,l,m,lx,rx);
int rq=query(2*v+2,m,r,lx,rx);
return max(lq,rq);
}
int query(int l, int r) {
return query(0,0,sz,l,r);
}
void upd(int v, int l, int r, int i) {
if (r-l==1) return;
int m=(l+r)>>1;
if (i<m) upd(2*v+1,l,m,i);
else upd(2*v+2,m,r,i);
t[v]=max(t[2*v+1],t[2*v+2]);
}
void set(int i, int x) {
t[sz-1+i]=x;
upd(0,0,sz,i);
}
};
sgt st(5e5+5);
int query() {
#define int long long
int z=1;
int b=0;
pi mx={0,1};
int last=n;
s.insert(0);
for (auto v:s) {
int i=-v;
if (z>1e9) break;
int y=st.query(i,n);
if (y*mx.s>mx.f*z) {
b=i;
mx={y,z};
}
z*=a[i];
last=i;
}
int p=ft.sum(b);
int y=st.query(b,n);
return (p*y)%mod;
#undef int
}
int init(int _n, int x[], int y[]) {
n=_n;
forn(i,n) a[i]=x[i], c[i]=y[i];
forn(i,n) ft.add(i,a[i]);
forn(i,n) if (a[i]>1) s.insert(-i);
forn(i,n) st.set(i,c[i]);
return query();
}
int updateX(int i, int x) {
if (a[i]>1) s.erase(s.find(-i));
ft.add(i,inv(a[i]));
a[i]=x;
if (a[i]>1) s.insert(-i);
ft.add(i,a[i]);
return query();
}
int updateY(int i, int x) {
c[i]=x;
st.set(i,c[i]);
return query();
}
