#include <bits/stdc++.h>
#include "horses.h"
// #include "grader.cpp"
using namespace std;
using ll = long long;
const int md = (int)1e9 + 7;
int n, Z = 1;
vector<int> x(n), y(n);
int pw(int x, int y) {
int res = 1;
while (y) {
if (y & 1) res = (ll)res * x % md;
y >>= 1;
x = (ll)x * x % md;
}
return res;
}
int init(int N, int a[], int b[]) {
n = N;
x = y = vector<int>(n);
for (int i = 0; i < n; i++) {
x[i] = a[i]; y[i] = b[i];
}
for (int i = 0; i < max(n - 60, 0); i++)
Z = (ll)Z * x[i] % md;
ll pr = 1;
int X = Z, ans = 0, lst = -1;
for (int i = max(n - 60, 0); i < n; i++) {
pr *= x[i];
if (md < pr || !~lst || y[lst] < pr * y[i]) {
X = (ll)X * (pr % md) % md; pr = 1;
ans = (ll)X * y[i] % md; lst = i;
}
}
return ans;
}
int updateX(int pos, int val) {
if (pos < max(n - 60, 0)) Z = ((ll)Z * pw(x[pos], md - 2) % md) * val % md;
x[pos] = val;
ll pr = 1;
int X = Z, ans = 0, lst = -1;
for (int i = max(n - 60, 0); i < n; i++) {
pr *= x[i];
if (md < pr || !~lst || y[lst] < pr * y[i]) {
X = (ll)X * (pr % md) % md; pr = 1;
ans = (ll)X * y[i] % md; lst = i;
}
}
return ans;
}
int updateY(int pos, int val) {
y[pos] = val;
ll pr = 1;
int X = Z, ans = 0, lst = -1;
for (int i = max(n - 60, 0); i < n; i++) {
pr *= x[i];
if (md < pr || !~lst || y[lst] < pr * y[i]) {
X = (ll)X * (pr % md) % md; pr = 1;
ans = (ll)X * y[i] % md; lst = i;
}
}
return ans;
}
