#include "horses.h"
#include <bits/stdc++.h>
#define se second
#define fi first
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;
const int MOD = 1e9 + 7;
const int B = 32;
const int C = 1e9;
int n, m, pref;
vector<ll> vec, x, y;
ll exp(ll a, ll b) {
assert(b >= 0);
a %= MOD; // note: m * m must be less than 2^63 to avoid ll overflow
ll res = 1;
while (b > 0) {
if (b % 2 == 1) { res = res * a % MOD; }
a = a * a % MOD;
b /= 2;
}
return res;
}
int calc() {
ll prev = 1, ans = 0;
int cnt = n-m;
for(int i=n-1; i>=n-m; --i) {
prev *= x[i];
if(prev >= C) {
cnt = i;
break;
}
}
prev = 1;
for(int i=cnt; i<n; ++i) {
prev *= x[i];
ll tmp = prev * y[i];
ans = max(ans,tmp);
}
ans %= MOD;
for(int i=n-m; i<cnt; ++i) ans = (1ll * ans * x[i]) % MOD;
ans = (1ll * ans * pref) % MOD;
return ans;
}
int init(int N, int X[], int Y[]) {
x.resize(N);
y.resize(N);
n = N;
for(int i=0; i<N; ++i) {
x[i] = X[i];
y[i] = Y[i];
}
if(N < B) m = N;
else m = B;
pref = 1;
for(int i=0; i<N-m; ++i) pref = (1ll * pref * X[i]) % MOD;
vec.resize(m);
return calc();
}
int updateX(int pos, int val) {
if(pos < n-m) {
pref = (1ll * pref * exp(x[pos], MOD-2));
pref = (1ll * pref * val);
}
x[pos] = val;
return calc();
}
int updateY(int pos, int val) {
y[pos] = val;
return calc();
}
