#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef unsigned long long ull;
typedef pair<double, double> pd;
typedef pair<int, int> pi;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll; typedef pair<ll, pi> plp;
typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF * 2;
const int MOD = 1e9 + 7;
int N, *X, *Y;
ll myMul(ll x, ll y) {
if(x < MOD && y < MOD) return x*y;
return LINF;
}
struct MUL{
int P; vector<ll> val, mod;
void merge(int i) {
val[i] = myMul(val[i*2], val[i*2+1]);
mod[i] = mod[i*2] * mod[i*2+1] % MOD;
}
MUL() {}
MUL(int n, int nr[]) {
for(P=1; P<n; P<<=1);
val = mod = vector<ll>(2*P, 1ll);
for(int i=0; i<n; i++) val[P+i] = mod[P+i] = nr[i];
for(int i=P-1; i>=1; i--) merge(i);
}
void updateX(int v, int k) {
X[v] = k;
v += P;
val[v] = mod[v] = k;
while(v/=2) merge(v);
}
ll getMul(int a, int b) {
ll res = 1;
for(a+=P, b+=P; a<=b; a>>=1, b>>=1) {
if(a%2==1) res = myMul(res, val[a++]);
if(b%2==0) res = myMul(res, val[b--]);
}
return res;
}
ll getMod(int a, int b) {
ll res = 1;
for(a+=P, b+=P; a<=b; a>>=1, b>>=1) {
if(a%2==1) res = res * mod[a++] % MOD;
if(b%2==0) res = res * mod[b--] % MOD;
}
return res;
}
}Mul;
struct IDX{
int P; vector<int> ix;
void merge(int i) {
int l = ix[i*2], r = ix[i*2+1];
int res = -1;
if(r == -1) res = l;
else{
ll mul = Mul.getMul(l+1, r);
if(mul >= MOD) res = r;
else{
if(Y[l] >= mul * Y[r]) res = l;
else res = r;
}
}
ix[i] = res;
}
IDX() {}
IDX(int n, int nr[]) {
for(P=1; P<n; P<<=1);
ix = vector<int>(2*P, -1);
for(int i=0; i<n; i++) ix[P+i] = i;
for(int i=P-1; i>=1; i--) merge(i);
}
void updateX(int v, int k) {
v += P;
while(v/=2) merge(v);
}
void updateY(int v, int k) {
Y[v] = k;
v += P;
while(v/=2) merge(v);
}
int getMax() {return ix[1];}
}Idx;
int getAns() {
int ans = Idx.getMax();
return Mul.getMod(0, ans) * Y[ans] % MOD;
}
int init(int n, int x[], int y[]) {
N = n; X = x; Y = y;
Mul = MUL(n, x);
Idx = IDX(n, y);
return getAns();
}
int updateX(int pos, int val) {
Mul.updateX(pos, val);
Idx.updateX(pos, val);
return getAns();
}
int updateY(int pos, int val) {
Idx.updateY(pos, val);
return getAns();
}
