#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int MOD = 1e9+7;
vector<pair<long long, bool>> segX;
vector<int> segY;
vector<int> Y;
int S;
inline int left(int i){return i*2+1;}
inline int right(int i){return (i+1)*2;}
inline int father(int i){return (i-1)/2;}
pair<long long, bool> mergeX(pair<long long, bool> a, pair<long long, bool> b){
long long val = (a.first * b.first);
bool o = val >= MOD || a.second || b.second;
return {val % MOD, o};
}
pair<long long, bool> queryX(int pos, int l, int h, int a, int b){
if(h < a || l > b) return {1, false};
if(l >= a && b >= h) return segX[pos];
int mid = (l+h)/2;
return mergeX(queryX(left(pos), l, mid, a, b), queryX(right(pos), mid+1, h, a, b));
}
int mergeY(int a, int b){
auto query = queryX(0, 0, S/2, a+1, b);
if(query.second) return b;
return Y[a] < 1LL * query.first * Y[b] ? b : a;
}
int init(int N, int X[], int Y[]) {
S = (1 << (int)ceil(log2(N) + 1)) - 1;
segX.resize(S, {1, false});
segY.resize(S, N);
::Y.resize(N);
for(int i=0; i<N; i++) ::Y[i] = Y[i];
::Y.push_back(0);
iota(segY.begin()+S/2, segY.begin()+S/2+N, 0);
for(int i=0; i<N; i++) segX[i+S/2] = {X[i], false};
for(int i=S/2-1; i>=0; i--){
segX[i] = mergeX(segX[left(i)], segX[right(i)]);
segY[i] = mergeY(segY[left(i)], segY[right(i)]);
}
return 1LL * queryX(0, 0, S/2, 0, segY[0]).first * Y[segY[0]] % MOD;
}
int updateX(int i, int val) {
i += S/2;
segX[i].first = val;
while(i != 0){
i = father(i);
segX[i] = mergeX(segX[left(i)], segX[right(i)]);
segY[i] = mergeY(segY[left(i)], segY[right(i)]);
}
return 1LL * queryX(0, 0, S/2, 0, segY[0]).first * Y[segY[0]] % MOD;
}
int updateY(int i, int val) {
Y[i] = val;
i += S/2;
while(i != 0){
i = father(i);
segX[i] = mergeX(segX[left(i)], segX[right(i)]);
segY[i] = mergeY(segY[left(i)], segY[right(i)]);
}
return 1LL * queryX(0, 0, S/2, 0, segY[0]).first * Y[segY[0]] % MOD;
}
