#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 14;
const int MOD = 1e9 + 7;
long long x[MAXN];
long long y[MAXN];
int n;
struct segtr {
long double ans = 0, lazy = 0;
bool push = 0;
int id;
} st[4 * MAXN];
void push_down(int idx) {
if(st[idx].push) {
st[2*idx+1].ans += st[idx].lazy;
st[2*idx+1].lazy += st[idx].lazy;
st[2*idx+1].push = 1;
st[2*idx+2].ans += st[idx].lazy;
st[2*idx+2].lazy += st[idx].lazy;
st[2*idx+2].push = 1;
st[idx].push = 0;
st[idx].lazy = 0;
}
}
void build(int l, int r, int tar) {
if(l == r) {
st[tar].id = l;
return;
}
int mid = (l + r) >> 1;
build(l, mid, 2*tar + 1);
build(mid+1, r, 2*tar + 2);
st[tar].id = st[2*tar+1].id;
}
void u(int l, int r, int constl, int constr, int idx, long double uwu) {
if(l <= constl && constr <= r) {
st[idx].ans += uwu;
st[idx].lazy += uwu;
st[idx].push = 1;
return;
}
push_down(idx);
int mid = (constl + constr) >> 1;
if(mid < l || r < constl) u(l, r, mid + 1, constr, 2 * idx + 2, uwu);
else if(constr < l || r < mid+1) u(l, r, constl, mid, 2 * idx + 1, uwu);
else {
u(l, r, constl, mid, 2 * idx + 1, uwu);
u(l, r, mid + 1, constr, 2 * idx + 2, uwu);
}
st[idx].ans = max(st[2*idx+1].ans, st[2*idx+2].ans);
if(abs(st[idx].ans - st[2*idx+1].ans) < abs(st[idx].ans - st[2*idx+2].ans)) st[idx].id = st[2*idx+1].id;
else st[idx].id = st[2*idx+2].id;
}
pair<long double, int> qu(int l, int r, int constl, int constr, int idx) {
if(l <= constl && constr <= r) return {st[idx].ans, st[idx].id};
push_down(idx);
int mid = (constl + constr) >> 1;
if(mid < l || r < constl) return qu(l, r, mid+1, constr, 2*idx+2);
else if(constr < l || r < mid+1) return qu(l, r, constl, mid, 2*idx+1);
else {
return max(qu(l, r, constl, mid, 2*idx+1), qu(l, r, mid+1, constr, 2*idx+2));
}
}
long long bm(long long b, long long p) {
if(p==0) return 1 % MOD;
long long r = bm(b, p >> 1);
if(p&1) return (((r*r) % MOD) * b) % MOD;
return (r*r) % MOD;
}
long long inv(long long b) {
return bm(b, MOD-2);
}
long long bit[MAXN];
// To use
void mul(int x, long long y) {
x++;
for(;x<MAXN;x+=x&-x) bit[x] = (bit[x] * y) % MOD;
}
void div(int x, long long y) {
x++;
long long invy = inv(y);
for(;x<MAXN;x+=x&-x) bit[x] = (bit[x] * invy) % MOD;
}
long long prod(int x) {
x++;
long long ret = 1;
for(;x; x-=x&-x) ret = (ret * bit[x]) % MOD;
return ret;
}
void x_upd(int l, int r, long double v) {
u(l, r, 0, MAXN - 1, 0, v);
}
long double thelog(int x) {
return 1000.0 * log2(x);
}
int find_best_index() {
return qu(0, n - 1, 0, MAXN - 1, 0).second;
}
int eval() {
int fbi = find_best_index();
long long ans = (prod(fbi) * y[fbi]) % MOD;
//cout << fbi << ' ' << prod(fbi) << ' ' << y[fbi] << '\n';
return (int) ans;
}
int init(int N, int X[], int Y[]) {
n = N;
build(0, MAXN - 1, 0);
for(int i=0; i<n; i++) x[i] = X[i];
for(int i=0; i<n; i++) y[i] = Y[i];
for(int i=0; i<=n; i++) bit[i] = 1;
for(int i=0; i<n; i++) mul(i, x[i]);
long double thelogsum = 0;
for(int i=0; i<n; i++) {
thelogsum += thelog(x[i]);
long double simp = thelogsum + thelog(y[i]);
x_upd(i, i, simp);
}
return eval();
}
int updateX(int pos, int val) {
div(pos, x[pos]);
x_upd(pos, n - 1, thelog(val)-thelog(x[pos]));
x[pos] = val;
mul(pos, x[pos]);
return eval();
}
int updateY(int pos, int val) {
x_upd(pos, pos, thelog(val)-thelog(y[pos]));
y[pos] = val;
return eval();
}
