#include "horses.h"
#include <vector>
#include <algorithm>
#define v vector
#define ll long long
#define fi first
#define se second
#define MOD ((ll) 1000000007)
#define INF ((ll) 1000000001)
using namespace std;
int *x;
int *y;
int n;
// Subtask 1
// int solve() {
// int ma = 0;
// int pop = 1;
// for(int i=0; i<n; i++) {
// pop*=x[i];
// ma = max(ma, pop*y[i]);
// }
// return ma%MOD;
// }
// int init(int N, int X[], int Y[]) {
// n = N;
// x = X;
// y = Y;
// return solve();
// }
// int updateX(int pos, int val) {
// x[pos] = val;
// return solve();
// }
// int updateY(int pos, int val) {
// y[pos] = val;
// return solve();
// }
//Subtask 2
// int solve() {
// int max_i = n-1;
// ll pop = x[n-1];
// for(int i=n-2; i>=0; i--) {
// if (y[i] > y[max_i]*pop) {
// max_i = i;
// pop=1;
// }
// pop = min(pop*x[i], INF);
// }
// pop=1;
// for(int i=0; i<=max_i; i++){
// pop = (pop*x[i])%MOD;
// }
// return (int) (pop*y[max_i])%MOD;
// }
// int init(int N, int X[], int Y[]) {
// n = N;
// x = X;
// y = Y;
// return solve();
// }
// int updateX(int pos, int val) {
// x[pos] = val;
// return solve();
// }
// int updateY(int pos, int val) {
// y[pos] = val;
// return solve();
// }
// Subtask 3
// v<ll> xs_mults;
// ll query_xs(int L, int R, int l, int r, int index) {
// if (r<L || l>R) return 1;
// if (l>=L and r<=R) return xs_mults[index];
// int mid = (l+r)/2;
// ll subl = query_xs(L, R, l, mid, index*2);
// ll subr = query_xs(L, R, mid+1, r, index*2+1);
// return (subl*subr)%MOD;
// }
// void update_xs(int pos, int value, int l, int r, int index) {
// int mid = (l+r)/2;
// if (l==r){
// xs_mults[index] = value;
// return;
// }
// if (pos <= mid){
// update_xs(pos, value, l, mid, index*2);
// } else {
// update_xs(pos, value, mid+1, r, index*2+1);
// }
// xs_mults[index] = (xs_mults[index*2]*xs_mults[index*2+1])%MOD;
// }
// int solve() {
// int max_i = n-1;
// ll pop = x[n-1];
// for(int i=n-2; i>=0 && i>=n-30; i--) {
// if (y[i] > y[max_i]*pop) {
// max_i = i;
// pop=1;
// }
// pop = min(pop*x[i], INF);
// }
// ll mult = query_xs(0, max_i, 0, n-1, 1);
// return (int) ((mult*y[max_i])%MOD);
// }
// int init(int N, int X[], int Y[]) {
// n = N;
// x = X;
// y = Y;
// xs_mults = v<ll> (4*n, 1);
// for(int i=0; i<n; i++) {
// update_xs(i, x[i], 0, n-1, 1);
// }
// return solve();
// }
// int updateX(int pos, int val) {
// x[pos] = val;
// update_xs(pos, val, 0, n-1, 1);
// return solve();
// }
// int updateY(int pos, int val) {
// y[pos] = val;
// return solve();
// }
// Subtask 5
v<ll> xs_mod;
v<pair<int, pair<ll, ll>>> tree;
ll query_xs_mod(int L, int R, int l, int r, int index) {
if (r<L || l>R) return 1;
if (l>=L and r<=R) return xs_mod[index];
int mid = (l+r)/2;
ll subl = query_xs_mod(L, R, l, mid, index*2);
ll subr = query_xs_mod(L, R, mid+1, r, index*2+1);
return (subl*subr)%MOD;
}
void update_xs_mod(int pos, int value, int l, int r, int index) {
int mid = (l+r)/2;
if (l==r){
xs_mod[index] = value;
return;
}
if (pos <= mid){
update_xs_mod(pos, value, l, mid, index*2);
} else {
update_xs_mod(pos, value, mid+1, r, index*2+1);
}
xs_mod[index] = (xs_mod[index*2]*xs_mod[index*2+1])%MOD;
}
void update_tree(int pos, int x_value, int y_value, int l, int r, int index) {
if (l==r) {
x[pos] = x_value;
y[pos] = y_value;
tree[index] = {pos, {x_value, 1}};
return;
}
int mid = (l+r)/2;
if (pos <= mid){
update_tree(pos, x_value, y_value, l, mid, index*2);
} else {
update_tree(pos, x_value, y_value, mid+1, r, index*2+1);
}
pair<int, pair<ll, ll>> subl = tree[index*2];
pair<int, pair<ll, ll>> subr = tree[index*2+1];
if (subr.fi == -1) {
tree[index] = subl;
return;
}
ll growth = min(INF, subl.se.se * subr.se.fi);
if (y[subl.fi] > growth*y[subr.fi]) {
tree[index] = {subl.fi, {subl.se.fi, min(INF, growth*subr.se.se)}};
} else {
tree[index] = {subr.fi, {min(INF, subl.se.fi*growth), subr.se.se}};
}
}
int solve() {
int max_i = tree[1].fi;
ll pop = query_xs_mod(0, max_i, 0, n-1, 1);
return (int) ((pop*y[max_i])%MOD);
}
int init(int N, int X[], int Y[]) {
n = N;
x = X;
y = Y;
xs_mod = v<ll> (4*n, 1);
tree = v<pair<int, pair<ll,ll>>> (4*n, {-1, {1, 1}});
for (int i=0; i<n; i++) {
update_xs_mod(i, X[i], 0, n-1, 1);
update_tree(i, X[i], Y[i], 0, n-1, 1);
}
return solve();
}
int updateX(int pos, int val) {
update_tree(pos, val, y[pos], 0, n-1, 1);
update_xs_mod(pos, val, 0, n-1, 1);
return solve();
}
int updateY(int pos, int val) {
update_tree(pos, x[pos], val, 0, n-1, 1);
return solve();
}
// Shouldn't work but does :/
// v<ll> xs_mod;
// v<ll> xs_trunc;
// v<int> ys_max;
// ll query_xs_mod(int L, int R, int l, int r, int index) {
// if (r<L || l>R) return 1;
// if (l>=L and r<=R) return xs_mod[index];
// int mid = (l+r)/2;
// ll subl = query_xs_mod(L, R, l, mid, index*2);
// ll subr = query_xs_mod(L, R, mid+1, r, index*2+1);
// return (subl*subr)%MOD;
// }
// void update_xs_mod(int pos, int value, int l, int r, int index) {
// if (l==r) {
// xs_mod[index] = value;
// return;
// }
// int mid = (l+r)/2;
// if (pos <= mid){
// update_xs_mod(pos, value, l, mid, index*2);
// } else {
// update_xs_mod(pos, value, mid+1, r, index*2+1);
// }
// xs_mod[index] = (xs_mod[index*2]*xs_mod[index*2+1])%MOD;
// }
// ll query_xs_trunc(int L, int R, int l, int r, int index) {
// if (r<L || l>R) return 1;
// if (l>=L and r<=R) return xs_trunc[index];
// int mid = (l+r)/2;
// ll subl = query_xs_trunc(L, R, l, mid, index*2);
// ll subr = query_xs_trunc(L, R, mid+1, r, index*2+1);
// return min(INF, subl*subr);
// }
// void update_xs_trunc(int pos, int value, int l, int r, int index) {
// if (l==r) {
// xs_trunc[index] = value;
// return;
// }
// int mid = (l+r)/2;
// if (pos <= mid){
// update_xs_trunc(pos, value, l, mid, index*2);
// } else {
// update_xs_trunc(pos, value, mid+1, r, index*2+1);
// }
// xs_trunc[index] = min(INF, xs_trunc[index*2]*xs_trunc[index*2+1]);
// }
// int query_ys_max(int L, int R, int l, int r, int index) {
// if (r<L || l>R) return -1;
// if (l>=L and r<=R) return ys_max[index];
// int mid = (l+r)/2;
// int subl = query_ys_max(L, R, l, mid, index*2);
// int subr = query_ys_max(L, R, mid+1, r, index*2+1);
// if (subl == -1) return subr;
// if (subr == -1) return subl;
// if (y[subl] > y[subr]) return subl;
// return subr;
// }
// void update_ys_max(int pos, int value, int l, int r, int index) {
// if (l==r) {
// y[pos] = value;
// ys_max[index] = pos;
// return;
// }
// int mid = (l+r)/2;
// if (pos <= mid){
// update_ys_max(pos, value, l, mid, index*2);
// } else {
// update_ys_max(pos, value, mid+1, r, index*2+1);
// }
// int subl = ys_max[index*2];
// int subr = ys_max[index*2+1];
// int ans = 0;
// if (subl == -1) ans = subr;
// else if (subr == -1) ans = subl;
// else if (y[subl] > y[subr]) ans = subl;
// else ans = subr;
// ys_max[index] = ans;
// }
// int solve() {
// int max_i = query_ys_max(0, n-1, 0, n-1, 1);
// int cur = max_i;
// while (cur<n-1) {
// cur = query_ys_max(cur+1, n-1, 0, n-1, 1);
// ll pop = query_xs_trunc(max_i+1, cur, 0, n-1, 1);
// if (y[cur]*pop > y[max_i]) {
// max_i = cur;
// }
// }
// ll pop = query_xs_mod(0, max_i, 0, n-1, 1);
// return (int) ((pop*y[max_i])%MOD);
// }
// int init(int N, int X[], int Y[]) {
// n = N;
// y = Y;
// xs_trunc = v<ll> (4*n, 1);
// xs_mod = v<ll> (4*n, 1);
// ys_max = v<int> (4*n, 0);
// for (int i=0; i<n; i++) {
// update_xs_mod(i, X[i], 0, n-1, 1);
// update_xs_trunc(i, X[i], 0, n-1, 1);
// update_ys_max(i, Y[i], 0, n-1, 1);
// }
// return solve();
// }
// int updateX(int pos, int val) {
// update_xs_mod(pos, val, 0, n-1, 1);
// update_xs_trunc(pos, val, 0, n-1, 1);
// return solve();
// }
// int updateY(int pos, int val) {
// update_ys_max(pos, val, 0, n-1, 1);
// return solve();
// }
