#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using ll = long long;
using pr = pair<int, int>;
const int MOD = 1e9+7, MAXA = 1e6;
vector<ll> X, Y;
struct segtree{
vector<ll> x, y;
int n;
void init(int N) {
n = N;
x.assign(4*n+5, 1);
y.assign(4*n+5, 1);
build(1, 1, n);
}
int L(int i) {return i << 1;}
int R(int i) {return i << 1 | 1;}
void pull(int i, int l, int r) {
int m = (l + r) >> 1;
x[i] = (x[L(i)] * x[R(i)]) % MOD;
y[i] = max(y[L(i)], (x[L(i)] * y[R(i)]) % MOD);
}
void build(int i, int l, int r) {
if (l == r) {
x[i] = X[l];
y[i] = (Y[l] * X[l]) % MOD;
return;
}
int m = (l + r) >> 1;
build(L(i), l, m);
build(R(i), m+1, r);
pull(i, l, r);
}
void updatex(int pos, int val) {updatex(1, 1, n, pos, val);}
void updatex(int i, int l, int r, int pos, int val) {
if (l == r) {
X[i] = val;
return;
}
int m = (l + r) >> 1;
if (pos <= m) updatex(L(i), l, m, pos, val);
else updatex(R(i), m+1, r, pos, val);
pull(i, l, r);
}
void updatey(int pos, int val) {updatey(1, 1, n, pos, val);}
void updatey(int i, int l, int r, int pos, int val) {
if (l == r) {
X[i] = val;
return;
}
int m = (l + r) >> 1;
if (pos <= m) updatey(L(i), l, m, pos, val);
else updatey(R(i), m+1, r, pos, val);
pull(i, l, r);
}
} seg;
int init(int N, int xx[], int yy[]) {
X.resize(N+1);
Y.resize(N+1);
for (int i = 0; i < N; i++) {
X[i+1] = xx[i];
Y[i+1] = yy[i];
}
seg.init(N);
return seg.y[1];
}
int updateX(int pos, int val) {
pos++;
seg.updatex(pos, val);
return seg.y[1];
}
int updateY(int pos, int val) {
pos++;
seg.updatey(pos, val);
return seg.y[1];
}
