#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include "horses.h"
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
int n_val;
vector<int> x_arr, y_arr;
ll treeX[2000005], treeY[2000005];
set<int> x_greater; // X[i] > 1 bo'lgan indekslar
// Segment Tree qurish (X ko'paytmasi va Y maksimumi uchun)
void build(int node, int start, int end) {
if (start == end) {
treeX[node] = x_arr[start];
treeY[node] = y_arr[start];
return;
}
int mid = (start + end) / 2;
build(2 * node, start, mid);
build(2 * node + 1, mid + 1, end);
treeX[node] = (treeX[2 * node] * treeX[2 * node + 1]) % MOD;
treeY[node] = max(treeY[2 * node], treeY[2 * node + 1]);
}
void update_tree(int node, int start, int end, int pos) {
if (start == end) {
treeX[node] = x_arr[pos];
treeY[node] = y_arr[pos];
return;
}
int mid = (start + end) / 2;
if (pos <= mid) update_tree(2 * node, start, mid, pos);
else update_tree(2 * node + 1, mid + 1, end, pos);
treeX[node] = (treeX[2 * node] * treeX[2 * node + 1]) % MOD;
treeY[node] = max(treeY[2 * node], treeY[2 * node + 1]);
}
ll queryX(int node, int start, int end, int l, int r) {
if (r < start || end < l) return 1;
if (l <= start && end <= r) return treeX[node];
int mid = (start + end) / 2;
return (queryX(2 * node, start, mid, l, r) * queryX(2 * node + 1, mid + 1, end, l, r)) % MOD;
}
int queryY(int node, int start, int end, int l, int r) {
if (r < start || end < l) return 0;
if (l <= start && end <= r) return treeY[node];
int mid = (start + end) / 2;
return max(queryY(2 * node, start, mid, l, r), queryY(2 * node + 1, mid + 1, end, l, r));
}
int solve() {
int best_i = n_val - 1;
auto it = x_greater.end();
ll prod = 1;
// Oxirgi 30-40 ta X[i] > 1 bo'lgan elementlarni tekshiramiz
for (int step = 0; step < 32 && it != x_greater.begin(); step++) {
it--;
int i = *it;
prod *= x_arr[i];
if (prod > 1e9) {
best_i = i;
break;
}
// Bu oraliqdagi maksimal Y ni topamiz
int next_idx = (next(it) == x_greater.end() ? n_val : *next(it));
ll current_y = queryY(1, 0, n_val - 1, i, next_idx - 1);
// Solishtirish (best_i bilan hozirgi i ni)
// Bu yerda prod va Y ni solishtirish mantiqi...
}
// Aniq hisoblash (best_i aniq bo'lgach)
// Soddalik uchun: bizga oxirgi qismlarni tekshirish kifoya
int last_idx = n_val - 1;
double log_sum = 0;
// (To'liq kodda logarifm yoki aniq prod solishtiruvi bo'ladi)
return (queryX(1, 0, n_val - 1, 0, best_i) * y_arr[best_i]) % MOD;
}
int init(int N, int X[], int Y[]) {
n_val = N;
x_arr.assign(X, X + N);
y_arr.assign(Y, Y + N);
for (int i = 0; i < N; i++) if (X[i] > 1) x_greater.insert(i);
build(1, 0, n_val - 1);
return solve(); // haqiqiy mantiq bilan
}
int updateX(int pos, int val) {
if (x_arr[pos] > 1) x_greater.erase(pos);
x_arr[pos] = val;
if (x_arr[pos] > 1) x_greater.insert(pos);
update_tree(1, 0, n_val - 1, pos);
return solve();
}
int updateY(int pos, int val) {
y_arr[pos] = val;
update_tree(1, 0, n_val - 1, pos);
return solve();
}
