#include "horses.h"
#include <bits/stdc++.h>
#define se second
#define fi first
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;
const int MOD = 1e9 + 7;
const int MAX_N = 5e5 + 5;
struct Node {
int val = 1, X = 1, lazy = 1;
} segm[MAX_N];
ll exp(ll x, ll n) {
assert(n >= 0);
x %= MOD;
ll res = 1;
while (n > 0) {
if (n % 2 == 1) { res = res * x % MOD; }
x = x * x % MOD;
n /= 2;
}
return res;
}
void push_down(int pos, int l, int r) {
segm[pos].X = (1ll * segm[pos].lazy * segm[pos].X) % MOD;
if(l == r) {
segm[pos].val = (1ll * segm[pos].lazy * segm[pos].val) % MOD;
segm[pos].lazy = 1;
return;
}
segm[2*pos+1].lazy = (1ll * segm[2*pos+1].lazy * segm[pos].lazy) % MOD;
segm[2*pos+2].lazy = (1ll * segm[2*pos+2].lazy * segm[pos].lazy) % MOD;
segm[pos].lazy = 1;
}
void updatey(int pos, int l, int r, int x, int val) {
push_down(pos, l, r);
if(l == r) {
segm[pos].val = (1ll * val * segm[pos].X) % MOD;
return;
}
int m = (l+r)/2;
if(m >= x) updatey(2*pos+1, l, m, x, val);
else updatey(2*pos+2, m+1, r, x, val);
segm[pos].val = max(1ll * segm[2*pos+1].val, 1ll * segm[2*pos+1].X * segm[2*pos+2].val % MOD);
}
void updatex(int pos, int l, int r, int x, int val) {
if(r < x) return;
push_down(pos, l, r);
if(l >= x) {
segm[pos].lazy = (1ll * segm[pos].lazy * val) % MOD;
push_down(pos, l, r);
return;
}
int m = (l+r)/2;
updatex(2*pos+1, l, m, x, val);
updatex(2*pos+2, m+1, r, x, val);
push_down(2*pos+1, l, m);
push_down(2*pos+2, m+1, r);
segm[pos].val = max(1ll * segm[2*pos+1].val, 1ll * segm[2*pos+1].X * segm[2*pos+2].val % MOD);
segm[pos].X = (1ll * segm[2*pos+1].X * segm[2*pos+2].X) % MOD;
}
int N2;
vi X2;
int init(int N, int X[], int Y[]) {
X2.resize(N);
for(int i=0; i<N; ++i) {
updatex(1, 0, N-1, i, X[i]);
X2[i] = X[i];
updatey(1, 0, N-1, i, Y[i]);
}
N2 = N;
return segm[1].val;
}
int updateX(int pos, int val) {
updatex(1, 0, N2-1, pos, (1ll * exp(X2[pos], MOD-2) * val) % MOD);
X2[pos] = val;
return segm[1].val;
}
int updateY(int pos, int val) {
updatey(1, 0, N2-1, pos, val);
return segm[1].val;
}
