#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
static const int MAXN = 500000;
static const int MOD = 1000000007;
int N;
int Xarr[MAXN], Yarr[MAXN];
int prodSeg[4*MAXN], capSeg[4*MAXN];
int ySeg[4*MAXN];
int bestSeg[4*MAXN];
set<int> growths;
void buildProd(int node, int l, int r)
{
if (l == r)
{
prodSeg[node] = Xarr[l] % MOD;
capSeg[node] = min(Xarr[l], 1000000000);
}
else
{
int mid = (l + r) >> 1;
buildProd(node*2, l, mid);
buildProd(node*2+1, mid+1, r);
prodSeg[node] = int(1LL * prodSeg[node*2] * prodSeg[node*2+1] % MOD);
capSeg[node] = int(min(1000000000LL, 1LL * capSeg[node*2] * capSeg[node*2+1]));
}
}
int queryProd(int seg[], int capArr[], int ql, int qr, bool capFlag, int node_l, int node_r, int node)
{
if (qr < node_l || node_r < ql) return 1;
if (ql <= node_l && node_r <= qr)
{
return capFlag ? capArr[node] : seg[node];
}
int mid = (node_l + node_r) >> 1;
ll left = queryProd(seg, capArr, ql, qr, capFlag, node_l, mid, node*2);
ll right = queryProd(seg, capArr, ql, qr, capFlag, mid+1, node_r, node*2+1);
if (capFlag) return int(min(1000000000LL, left * right));
return int((left * right) % MOD);
}
void updateProd(int seg[], int capArr[], int pos, int val, int node_l, int node_r, int node)
{
if (node_l == node_r)
{
seg[node] = val % MOD;
capArr[node] = min(val, 1000000000);
}
else
{
int mid = (node_l + node_r) >> 1;
if (pos <= mid)
updateProd(seg, capArr, pos, val, node_l, mid, node*2);
else
updateProd(seg, capArr, pos, val, mid+1, node_r, node*2+1);
seg[node] = int(1LL * seg[node*2] * seg[node*2+1] % MOD);
capArr[node] = int(min(1000000000LL, 1LL * capArr[node*2] * capArr[node*2+1]));
}
}
void buildY(int node, int l, int r)
{
if (l == r)
{
ySeg[node] = l;
}
else
{
int mid = (l + r) >> 1;
buildY(node*2, l, mid);
buildY(node*2+1, mid+1, r);
int a = ySeg[node*2], b = ySeg[node*2+1];
ySeg[node] = (Yarr[a] >= Yarr[b] ? a : b);
}
}
void updateYseg(int node, int l, int r, int pos)
{
if (l == r) return;
int mid = (l + r) >> 1;
if (pos <= mid)
{
updateYseg(node*2, l, mid, pos);
}
else
{
updateYseg(node*2+1, mid+1, r, pos);
}
int a = ySeg[node*2], b = ySeg[node*2+1];
ySeg[node] = (Yarr[a] >= Yarr[b] ? a : b);
}
void buildBest(int node, int l, int r)
{
if (l == r)
{
bestSeg[node] = l;
}
else
{
int mid = (l + r) >> 1;
buildBest(node*2, l, mid);
buildBest(node*2+1, mid+1, r);
int L = bestSeg[node*2], R = bestSeg[node*2+1];
ll cap = queryProd(prodSeg, capSeg, L+1, R, true, 0, N-1, 1);
ll need = (Yarr[L] + Yarr[R] - 1LL) / Yarr[R];
bestSeg[node] = (cap >= need ? R : L);
}
}
void updateBest(int node, int l, int r, int pos)
{
if (l == r) return;
int mid = (l + r) >> 1;
if (pos <= mid)
{
updateBest(node*2, l, mid, pos);
}
else
{
updateBest(node*2+1, mid+1, r, pos);
}
int L = bestSeg[node*2], R = bestSeg[node*2+1];
ll cap = queryProd(prodSeg, capSeg, L+1, R, true, 0, N-1, 1);
ll need = (Yarr[L] + Yarr[R] - 1LL) / Yarr[R];
bestSeg[node] = (cap >= need ? R : L);
}
int init(int NN, int X[], int Y[])
{
N = NN;
for (int i = 0; i < N; i++)
{
Xarr[i] = X[i];
Yarr[i] = Y[i];
if (Xarr[i] != 1) growths.insert(i);
}
growths.insert(0);
buildProd(1, 0, N-1);
buildY(1, 0, N-1);
buildBest(1, 0, N-1);
int idx = bestSeg[1];
return int(1LL * queryProd(prodSeg, capSeg, 0, idx, false, 0, N-1, 1) * Yarr[idx] % MOD);
}
int updateX(int pos, int val)
{
Xarr[pos] = val;
if (val == 1 && pos != 0) growths.erase(pos);
else growths.insert(pos);
updateProd(prodSeg, capSeg, pos, val, 0, N-1, 1);
updateBest(1, 0, N-1, pos);
int idx = bestSeg[1];
return int(1LL * queryProd(prodSeg, capSeg, 0, idx, false, 0, N-1, 1) * Yarr[idx] % MOD);
}
int updateY(int pos, int val)
{
Yarr[pos] = val;
updateYseg(1, 0, N-1, pos);
updateBest(1, 0, N-1, pos);
int idx = bestSeg[1];
return int(1LL * queryProd(prodSeg, capSeg, 0, idx, false, 0, N-1, 1) * Yarr[idx] % MOD);
}
