#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007LL
#include "horses.h"
//hypothesis 1: There is no point in keeping a partial amount of horses. Sell all, or don't bother.
//Let's test this.
//Ok, should be confirmed (passed subtask 1)
//now, running product of X can be really big
//we need to determine the largest value in meow, where meow[i] = Y[i] * prefixProdX[i];
//honestly even Y[i] can be really big (10^9 for both X and Y)
//I also don't really want to touch floating point
//let our two comparison indices be A and B
//without loss of generality, let A < B
//then meow[A] = Y[A] * prefixProdX[A], meow[B] = Y[B] * prefixProdX[B]
//meow[A] < meow[B] iff
//Y[A] * prefixProdX[A] < Y[B] * prefixProdX[B]
//Y[A] < Y[B] * prefixProdX[B] / prefixProdX[A]
//Y[A] < Y[B] * rangeProdX(A+1, B)
//hmm both Y[A] and Y[B] are bounded by 10^9
//meaning if rangeProdX(A+1, B) ever exceeds 10^9, we can safely say meow[B] is greater
//Y is also bounded by 1
#define int long long
#define actlint int32_t
actlint *X, *Y;
int N;
bool st3 = true;
#define MAXN 500001
#define makeMid int mid = (s+e)/2
#define lc(x) (2*x)
#define rc(x) (2*x+1)
#define parent(x) (x/2)
typedef int stdata;
stdata ST[4*MAXN+1] = {0};
inline stdata combine(stdata x, stdata y){
return (x*y)%MOD;
}
void pointSet(int x, stdata y, int index=1, int s=0, int e=N-1){
makeMid;
if (s==e){ ST[index] = y; return; }
if (x <= mid) pointSet(x, y, lc(index), s, mid);
else pointSet(x, y, rc(index), mid+1, e);
ST[index] = combine(ST[lc(index)], ST[rc(index)]);
}
void pointAdd(int x, stdata y, int index=1, int s=0, int e=N-1){
makeMid;
if (s==e){ ST[index] += y; return; }
if (x <= mid) pointAdd(x, y, lc(index), s, mid);
else pointAdd(x, y, rc(index), mid+1, e);
ST[index] = combine(ST[lc(index)], ST[rc(index)]);
}
stdata query(int x, int y, int index=1, int s=0, int e=N-1){
makeMid;
if (s==x && e==y) return ST[index];
if (x <= mid && y > mid) return combine(query(x, mid, lc(index), s, mid), query(mid+1, y, rc(index), mid+1, e));
else if (x <= mid) return query(x, y, lc(index), s, mid);
else return query(x, y, rc(index), mid+1, e);
}
int calc(){
//this is bottleneck of code
//this takes O(N) time, which is too long since we cannot afford O(NM)
//problem that this is meant to solve:
//find max of Y[i] * prefixProdX[i] (in log n time?)
long long best = 0;
long long run = 1;
long long init = 0;
if (st3) init = max(N-33LL, 0LL), best = max(N-33LL, 0LL);
for (int i = init; i < N; i++){
run *= X[i];
if ((int)Y[best] < (int)Y[i] * run){
best = i;
run = 1;
}
}
run = query(0, best);
run *= Y[best]; run %= MOD;
return run;
}
actlint init(actlint hmN, actlint hmX[], actlint hmY[]) {
N = hmN;
X = hmX; Y = hmY;
for (int i = 0; i < N; i++){
if (X[i] < 2) st3 = false;
pointSet(i, X[i]);
}
return calc();
}
actlint updateX(actlint pos, actlint val) {
X[pos] = val;
if (val < 2) st3 = false;
pointSet(pos, val);
return calc();
}
actlint updateY(actlint pos, actlint val) {
Y[pos] = val;
return calc();
}
