#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<ll, ll> pll;
const ll LOG = 34;
const ll MOD = 1000000007;
const ll inf = 1e17;
#define db(x) cerr << #x << " = " << x << " | "
#define dbg(x) cerr << #x << " = " << x << "\n"
ll n, p;
vector<ll> x, y;
ll binexp(ll b, ll e) {
ll r = 1;
while (e) {
if (e & 1) r = (r * b) % MOD;
b = (b * b) % MOD;
e >>= 1;
}
return r;
}
int init(int N, int X[], int Y[]) {
n = N;
x.resize(n);
y.resize(n);
p = 1;
for (ll i = 0; i < n; i++) x[i] = X[i], y[i] = Y[i];
for (ll i = 0; i < n - LOG; i++) {
p = (p * x[i]) % MOD;
}
return updateX(0, x[0]);
}
bool mod(ll& x) {
if (x >= MOD) {
x %= MOD;
return 1;
}
return 0;
}
int updateX(int pos, int val) {
if (pos < n - LOG) {
p = p * binexp(x[pos], MOD - 2) % MOD;
p = p * val % MOD;
// x[pos] = val;
}
x[pos] = val;
ll res = x[n - 1] * y[n - 1];
bool up = mod(res);
ll st = max(n - LOG, 0LL);
for (ll i = n - 2; i >= st; i--) {
if (up) {
res = (res * x[i]) % MOD;
} else {
res = x[i] * max(res, y[i]);
up |= mod(res);
}
}
return (res * p) % MOD;
}
int updateY(int pos, int val) {
y[pos] = val;
return updateX(0, x[0]);
}
