#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = ll(1e9) + 7;
ll pot(ll a, ll b) {
if(b == 0)
return 1;
if(b % 2)
return pot(a, b - 1) * a % MOD;
ll tmp = pot(a, b / 2);
return tmp * tmp % MOD;
}
ll inv(ll x) {
return pot(x, MOD - 2);
}
struct SegmentTree {
int lv;
int d[1100007];
SegmentTree(int n) {
lv = 2;
while(lv < n + 2)
lv *= 2;
}
void insert(int i, int v) {
int w = i + lv;
d[w] = v;
w /= 2;
while(w) {
d[w] = max(d[2 * w], d[2 * w + 1]);
w /= 2;
}
}
int query(int a, int b) {
if(a > b) return 0;
int va = a + lv;
int vb = b + lv;
int res = max(d[va], d[vb]);
while(va / 2 != vb/ 2) {
if(va % 2 == 0)
res = max(res, d[va + 1]);
if(vb % 2 == 1)
res = max(res, d[vb - 1]);
}
return res;
}
void recalc() {
for(int i = lv - 1 ; i >= 1 ; i--)
d[i] = max(d[2 * i], d[2 * i + 1]);
}
};
int n;
int x[500007], y[500007];
ll all = 1;
int prv[500007], nxt[500007];
int max_to_nxt[500007];
set<int> S;
SegmentTree ST(500007);
int calc() {
int i = *prev(S.end());
ll pro = x[i];
while(pro <= ll(1e9) && i > 0) {
i = prv[i];
pro *= x[i];
}
ll pref = all * inv(pro % MOD) % MOD * x[i] % MOD;
ll local_res = 0, res;
ll mul = 1;
while(true) {
ll a = mul * max_to_nxt[i];
if(a > local_res) {
local_res = a;
res = a % MOD * pref % MOD;
}
if(!nxt[i])
break;
i = nxt[i];
mul *= x[i];
}
return res % MOD;
}
int init(int N, int X[], int Y[]) {
n = N;
int lst = -1;
int maxv = 0;
for(int i = 0 ; i < n ; i++) {
x[i] = X[i];
//~ x1[i] = 1;
y[i] = Y[i];
if(x[i] > 1 || i == 0) {
prv[i] = lst;
if(lst != -1) {
nxt[lst] = i;
max_to_nxt[lst] = maxv;
}
maxv = 0;
all *= x[i];
all %= MOD;
//~ x1[i] = inv(x[i]);
lst = i;
S.insert(i);
}
maxv = max(maxv, y[i]);
ST.d[ST.lv + i] = y[i];
}
max_to_nxt[lst] = maxv;
ST.recalc();
return calc();
}
void remove_special(int pos) {
if(pos == 0) return ;
auto it = S.lower_bound(pos);
int i1 = *prev(it);
int i2 = 0;
if(next(it) != S.end())
i2 = *next(it);
S.erase(pos);
nxt[i1] = i2;
if(i2) {
prv[i2] = i1;
max_to_nxt[i1] = ST.query(i1, i2 - 1);
} else
max_to_nxt[i1] = ST.query(i1, n - 1);
}
void add_special(int pos) {
if(pos == 0) return ;
auto it = S.lower_bound(pos);
int i2 = 0;
if(it != S.end())
i2 = *it;
int i1 = *prev(it);
S.insert(pos);
nxt[i1] = pos;
nxt[pos] = i2;
prv[pos] = -1;
if(i2)
prv[i2] = pos;
max_to_nxt[i1] = ST.query(i1, pos - 1);
if(i2)
max_to_nxt[pos] = ST.query(pos, i2 - 1);
else
max_to_nxt[pos] = ST.query(pos, n - 1);
}
int updateX(int pos, int val) {
all = all * inv(x[pos]) % MOD * val % MOD;
if(x[pos] == 1 && val > 1) {
x[pos] = val;
add_special(pos);
} else if(x[pos] > 1 && val == 1) {
x[pos] = val;
remove_special(pos);
} else
x[pos] = val;
return calc();
}
int updateY(int pos, int val) {
y[pos] = val;
ST.insert(pos, val);
auto it = S.upper_bound(pos);
int i = *prev(it);
if(nxt[i])
max_to_nxt[i] = ST.query(i, nxt[i] - 1);
else
max_to_nxt[i] = ST.query(i, n - 1);
return calc();
}
