#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using ll = long long;
using ld = long double;
using pr = pair<int, int>;
const int MOD = 1e9+7, MAXA = 1e6;
vector<ll> X, Y;
struct segtree{
vector<ll> x, y, ogy;
vector<ld> num, mx;
int n;
void init(int N) {
n = N;
x.assign(4*n+5, 0);
y.assign(4*n+5, 0);
ogy.assign(4*n+5, 0);
mx.assign(4*n+5, 0);
num.assign(4*n+5, 0);
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;
if (mx[L(i)] > (ld)(num[L(i)] + mx[R(i)])) {
y[i] = y[L(i)];
}
else {
y[i] = (x[L(i)] * y[R(i)]) % MOD;
}
num[i] = num[L(i)] + num[R(i)];
}
void build(int i, int l, int r) {
if (l == r) {
x[i] = X[l];
ogy[i] = Y[l];
y[i] = (Y[l] * X[l]) % MOD;
num[i] = log2(x[i]);
mx[i] = num[i] +log2(ogy[i]);
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, ll val) {updatex(1, 1, n, pos, val);}
void updatex(int i, int l, int r, int pos, ll val) {
if (l == r) {
x[i] = val;
y[i] = (ogy[i] * x[i]) % MOD;
num[i] = log2(x[i]);
mx[i] = num[i] + log2(ogy[i]);
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, ll val) {updatey(1, 1, n, pos, val);}
void updatey(int i, int l, int r, int pos, ll val) {
if (l == r) {
ogy[i] = val;
y[i] = (val * x[i]) % MOD;
num[i] = log2(x[i]);
mx[i] = num[i] + log2(ogy[i]);
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];
}
