#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 = 33;
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;
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) {
ll res = x[n - 1] * y[n - 1];
bool up = mod(res);
x[pos] = val;
ll st = max(n - LOG, 0LL);
for (ll i = n - 2; i >= st; i--) {
if (up) {
res = res * x[i];
res = mod(res);
} 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]);
}
