#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
const int MOD = 1e9 + 7;
int N, X[500005], Y[500005];
struct node {
node *left, *right;
int S, E;
ld pv;
pair<ld, int> val;
node(int _s, int _e) : S(_s), E(_e), pv(0) {
if (S == E) {
val = make_pair(0., S);
return;
}
int M = (S + E) >> 1;
left = new node(S, M);
right = new node(M + 1, E);
val = max(left->val, right->val);
}
void prop() {
if (S == E || pv == 0.) return;
left->pv += pv;
left->val.first += pv;
right->pv += pv;
right->val.first += pv;
pv = 0.;
}
void upd(int l, int r, ld v) {
if (l > E || r < S) return;
if (l <= S && E <= r) {
val.first += v;
pv += v;
return;
}
prop();
left->upd(l, r, v);
right->upd(l, r, v);
val = max(left->val, right->val);
}
} *root;
struct node2 {
node2 *left, *right;
int S, E, val, pv;
node2(int _s, int _e) : S(_s), E(_e), val(1), pv(1) {
if (S == E) return;
int M = (S + E) >> 1;
left = new node2(S, M);
right = new node2(M + 1, E);
}
void prop() {
if (S == E || pv == 1) return;
left->pv = ((ll)left->pv * (ll)pv) % MOD;
left->val = ((ll)left->val * (ll)pv) % MOD;
right->pv = ((ll)right->pv * (ll)pv) % MOD;
right->val = ((ll)right->val * (ll)pv) % MOD;
pv = 1;
}
void upd(int l, int r, int v) {
if (l > E || r < S) return;
if (l <= S && E <= r) {
val = ((ll)val * (ll)v) % MOD;
pv = ((ll)pv * (ll)v) % MOD;
return;
}
prop();
left->upd(l, r, v);
right->upd(l, r, v);
}
int qry(int p) {
if (S == E) return val;
prop();
int M = (S + E) >> 1;
if (p <= M) return left->qry(p);
else return right->qry(p);
}
} *root2;
ld f(int n) {
return log(n) / 9.;
}
int init(int _N, int _X[], int _Y[]) {
N = _N;
for (int i = 1; i <= N; i++) X[i] = _X[i - 1];
for (int i = 1; i <= N; i++) Y[i] = _Y[i - 1];
root = new node(1, N);
for (int i = 1; i <= N; i++)
root->upd(i, N, f(X[i])), root->upd(i, i, f(Y[i]));
root2 = new node2(1, N);
for (int i = 1; i <= N; i++)
root2->upd(i, N, X[i]), root2->upd(i, i, Y[i]);
return root2->qry(root->val.second);
}
ll exp_mod(ll a, ll b) {
a %= MOD;
b %= (MOD - 1);
ll r = 1ll;
while (b) {
if (b & 1) r = r * a % MOD;
a = a * a % MOD;
b >>= 1ll;
}
assert(r <= INT_MAX);
return r;
}
int updateX(int pos, int val) {
pos++;
root->upd(pos, N, -f(X[pos]));
root2->upd(pos, N, exp_mod(X[pos], MOD - 2));
X[pos] = val;
root->upd(pos, N, f(X[pos]));
root2->upd(pos, N, X[pos]);
return root2->qry(root->val.second);
}
int updateY(int pos, int val) {
pos++;
root->upd(pos, pos, -f(Y[pos]));
root2->upd(pos, pos, exp_mod(Y[pos], MOD - 2));
Y[pos] = val;
root->upd(pos, pos, f(Y[pos]));
root2->upd(pos, pos, Y[pos]);
return root2->qry(root->val.second);
}
