#include "horses.h"
#include <bits/stdc++.h>
#define se second
#define fi first
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;
const int MOD = 1e9 + 7;
const ll MAX = 1e9 + 1;
vi x, y;
int n;
struct Node {
int p, p2, st;
};
vector<Node>segm;
void buildP(int pos, int l, int r) {
if(l == r) {
segm[pos].p = segm[pos].p2 = x[l];
return;
}
int m = (l+r)/2;
buildP(2*pos+1, l, m);
buildP(2*pos+2, m+1, r);
segm[pos].p = (1ll * segm[2*pos+1].p * segm[2*pos+2].p) % MOD;
segm[pos].p2 = min(MAX, 1ll * segm[2*pos+1].p2 * segm[2*pos+2].p2);
}
void updateP(int pos, int l, int r, int ind) {
if(l == r) {
segm[pos].p = segm[pos].p2 = x[ind];
return;
}
int m = (l+r)/2;
if(ind <= m) updateP(2*pos+1, l, m, ind);
else updateP(2*pos+2, m+1, r, ind);
segm[pos].p = (1ll * segm[2*pos+1].p * segm[2*pos+2].p) % MOD;
segm[pos].p2 = min(MAX, 1ll * segm[2*pos+1].p2 * segm[2*pos+2].p2);
}
int queryP(int pos, int l, int r, int ql, int qr, bool type) {
if(l > qr or r < ql) return 1;
if(l >= ql && r <= qr) return (type ? segm[pos].p2 : segm[pos].p);
int m = (l+r)/2;
ll tmp = 1ll * queryP(2*pos+1, l, m, ql, qr, type) * queryP(2*pos+2, m+1, r, ql, qr, type);
if(type) return min(MAX, tmp);
else return (tmp % MOD);
}
void build(int pos, int l, int r) {
if(l == r) {
segm[pos].st = l;
return;
}
int m = (l+r)/2;
build(2*pos+1, l, m);
build(2*pos+2, m+1, r);
int L = segm[2*pos+1].st, R = segm[2*pos+2].st;
if(queryP(1, 0, n-1, L+1, R, true) >= (int)ceil(y[L]/(double)y[R])) segm[pos].st = R;
else segm[pos].st = L;
}
void update(int pos, int l, int r, int ind) {
if(l == r) return;
int m = (l+r)/2;
if(ind <= m) update(2*pos+1, l, m, ind);
else update(2*pos+2, m+1, r, ind);
int L = segm[2*pos+1].st, R = segm[2*pos+2].st;
if(queryP(1, 0, n-1, L+1, R, true) >= (int)ceil(y[L]/(double)y[R])) segm[pos].st = R;
else segm[pos].st = L;
}
int calc() {
int ind = segm[1].st;
return (1ll * queryP(1, 0, n-1, 0, ind, false) * y[ind]) % MOD;
}
int init(int N, int X[], int Y[]) {
x.resize(N+1);
y.resize(N);
n = N;
segm.resize(6*N);
for(int i=0; i<N; ++i) {
x[i] = X[i];
y[i] = Y[i];
}
buildP(1, 0, n-1);
build(1, 0, n-1);
return calc();
}
int updateX(int pos, int val) {
x[pos] = val;
updateP(1, 0, n-1, pos);
update(1, 0, n-1, pos);
return calc();
}
int updateY(int pos, int val) {
y[pos] = val;
update(1, 0, n-1, pos);
return calc();
}
