#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple <ll,ll,ll> plll;
typedef vector <plll> vplll;
typedef pair <ll,ll> pll;
typedef vector <ll> vll;
typedef vector <pll> vpll;
typedef vector <vector <pll>> vvpll;
typedef vector <vector <ll>> vvll;
typedef vector <bool> vb;
typedef vector <vector <bool>> vvb;
#define loop(i, s, e) for (ll i = (s); i < (e); ++i)
#define loopr(i, e, s) for (ll i = (e)-1; i >= (s); --i)
#define all(a) a.begin(), a.end()
const ll inf = 1e9 + 7;
vll seg;
vector<double> xlog, ylog;
vll X, Y;
ll n;
ll sz=1;
vector<double> seg2, lazy2;
vector<ll> idx2;
void build() {
for (; sz<n; sz*=2);
seg.assign(2*sz, 1);
loop(i,0,n) seg[sz+i] = X[i];
loop(i,sz+n,2*sz) seg[i] = 1;
loopr(i,sz,1) seg[i] = (seg[2*i] * seg[2*i+1]) % inf;
}
void update(ll p, ll val) {
ll pos = sz + p;
seg[pos] = val;
for (pos/=2; pos>0; pos/=2) seg[pos] = (seg[2*pos] * seg[2*pos+1]) % inf;
}
ll query(ll rr) {
ll l = sz, r = sz + rr;
ll ans = 1;
while (l <= r) {
if (l%2 == 1) ans = (ans * seg[l++]) % inf;
if (r%2 == 0) ans = (ans * seg[r--]) % inf;
l/=2;
r/=2;
}
return ans;
}
void push2(ll p) {
if (lazy2[p] != 0) {
lazy2[2*p] += lazy2[p]; seg2[2*p] += lazy2[p];
lazy2[2*p+1] += lazy2[p]; seg2[2*p+1] += lazy2[p];
lazy2[p] = 0;
}
}
void pull2(ll p) {
if (seg2[2*p] >= seg2[2*p+1]) {
seg2[p] = seg2[2*p]; idx2[p] = idx2[2*p];
} else {
seg2[p] = seg2[2*p+1]; idx2[p] = idx2[2*p+1];
}
}
void build2() {
seg2.assign(2*sz, 0);
lazy2.assign(2*sz, 0);
idx2.assign(2*sz, 0);
double cur = 0;
loop(i,0,n) {
cur += xlog[i];
seg2[sz+i] = cur + ylog[i];
idx2[sz+i] = i;
}
loop(i,sz+n,2*sz) {
seg2[i] = -1e300;
idx2[i] = i - sz;
}
loopr(i,sz,1) pull2(i);
}
void rangeAdd(ll l, ll r, double v, ll p, ll lb, ll rb) {
if (r < lb || rb < l) return;
if (l <= lb && rb <= r) {
seg2[p] += v;
lazy2[p] += v;
return;
}
push2(p);
ll m = (lb + rb) / 2;
rangeAdd(l, r, v, 2*p, lb, m);
rangeAdd(l, r, v, 2*p+1, m+1, rb);
pull2(p);
}
ll getIdx() {
return idx2[1];
}
int init(int N, int X1[], int Y1[]) {
n = N;
xlog.resize(n);
ylog.resize(n);
X.resize(n);
Y.resize(n);
loop(i,0,n) {
xlog[i] = log2((double)X1[i]);
ylog[i] = log2((double)Y1[i]);
X[i] = X1[i];
Y[i] = Y1[i];
}
build();
build2();
ll idx = getIdx();
ll ansi = query(idx);
ansi = (ansi * Y[idx]) % inf;
return ansi;
}
int updateX(int pos, int val) {
double delta = log2((double)val) - xlog[pos];
xlog[pos] += delta;
X[pos] = val;
update(pos, val);
rangeAdd(pos, n-1, delta, 1, 0, sz-1);
ll idx = getIdx();
ll ansi = query(idx);
ansi = (ansi * Y[idx]) % inf;
return ansi;
}
int updateY(int pos, int val) {
double delta = log2((double)val) - ylog[pos];
ylog[pos] += delta;
Y[pos] = val;
rangeAdd(pos, pos, delta, 1, 0, sz-1);
ll idx = getIdx();
ll ansi = query(idx);
ansi = (ansi * Y[idx]) % inf;
return ansi;
}
