#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
#define MOD (1'000'000'000 + 7)
#define F(i, n) for(int i = 0; i < (n); i++)
#define F_reverse(i, n) for(int i = (n - 1); i >= 0; i--)
int N;
int X[500000], Y[500000];
set<int> idx_with_2plus;
struct segtree {
int segtree[1 << 21];
int segtree_size = 1;
const int zero = 0;
void init(int n) {
segtree_size = 1;
while(segtree_size < n) {
segtree_size <<= 1;
}
F(i, 2 * segtree_size) {
segtree[i] = zero;
}
}
int add(int a, int b) {
return max(a, b);
}
int get(int i, int window_l, int window_r, int l, int r) {
if(l <= window_l && window_r <= r) {
return segtree[i];
} else if((window_l <= l && l <= window_r) || (window_l <= r && r <= window_r)) {
int m = (window_l + window_r) / 2;
return add(get(i * 2 + 0, window_l,m,l,r), get(i * 2 + 1,m + 1,window_r,l,r));
} else {
return zero;
}
}
int get(int l, int r) {
if(l > r) {
return zero;
}
return get(1, 0, segtree_size - 1, l, r);
}
void set(int i, int data) {
i += segtree_size;
segtree[i] = data;
i /= 2;
while(i > 0) {
segtree[i] = add(segtree[i * 2 + 0], segtree[i * 2 + 1]);
i /= 2;
}
}
} ohio;
int64_t mod_pow(int64_t a, int64_t b) {
if(b == 0) {
return 1;
} else {
int64_t m = mod_pow(a, b / 2);
if(b & 1) {
return m * m % MOD * a % MOD;
} else {
return m * m % MOD;
}
}
}
int64_t mod_inv(int64_t a) {
return mod_pow(a, MOD - 2);
}
int64_t prod_all = 1;
int solve() {
__int128_t h = 1;
bool overflow = false;
int64_t ans = prod_all;
int prv = N;
for(auto it = idx_with_2plus.rbegin(); it != idx_with_2plus.rend(); --it) {
int i = *it;
ans = ans * mod_inv(X[i]) % MOD;
int best_Y = ohio.get(i, prv - 1);
if(best_Y > h) { // replace running product
h = best_Y;
}
h *= X[i];
prv = i;
if(h >= 1'000'000'000) {
overflow = true;
h %= MOD;
break;
}
}
if(!overflow) {
// edge case: remaining X are 1s
assert(ans == 1);
int best_Y = ohio.get(0, prv - 1);
if(best_Y > h) {
h = best_Y;
}
}
return ans * h % MOD;
}
int init(int _N, int _X[], int _Y[]) {
N = _N;
ohio.init(N);
F(i, N) {
X[i] = _X[i];
prod_all = prod_all * X[i] % MOD;
if(X[i] > 1) {
idx_with_2plus.insert(i);
}
Y[i] = _Y[i];
ohio.segtree[ohio.segtree_size + i] = Y[i];
}
F_reverse(i, ohio.segtree_size) {
ohio.segtree[i] = max(ohio.segtree[i * 2 + 0], ohio.segtree[i * 2 + 1]);
}
return solve();
}
int updateX(int pos, int val) {
if(X[pos] > 1 && val == 1) {
idx_with_2plus.erase(pos);
} else if(X[pos] == 1 && val > 1) {
idx_with_2plus.insert(pos);
}
prod_all = prod_all * mod_inv(val) % MOD;
X[pos] = val;
prod_all = prod_all * val % MOD;
return solve();
}
int updateY(int pos, int val) {
Y[pos] = val;
ohio.set(pos, val);
return solve();
}
