#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const int N = 500005, M = 1000000007;
int n;
struct ban
{
int ans;
int p;
int pl, pr, pp;
int y;
ban()
{
ans = 1;
p = 1;
pl = 1;
pr = 1;
}
ban(int x, int y)
{
ans = (x * 1LL * y) % M;
p = x;
pl = x;
pr = 1;
pp = x;
this->y = y;
}
};
ban t[N * 4];
ban mer(const ban& l, const ban& r)
{
ban res;
if (r.pl == M || l.pr == M)
{
res.ans = (l.p * 1LL * r.ans) % M;
res.p = (l.p * 1LL * r.p) % M;
res.pl = min(M * 1LL, l.pp * 1LL * r.pl);
res.pr = r.pr;
res.pp = min(M * 1LL, l.pp * 1LL * r.pp);
res.y = r.y;
}
else
{
if ((long double)l.y / r.y < (r.pl * 1LL * l.pr))
{
res.ans = (l.p * 1LL * r.ans) % M;
res.p = (l.p * 1LL * r.p) % M;
res.pl = min(M * 1LL, l.pp * 1LL * r.pl);
res.pr = r.pr;
res.pp = min(M * 1LL, l.pp * 1LL * r.pp);
res.y = r.y;
}
else
{
res.ans = l.ans;
res.p = (l.p * 1LL * r.p) % M;
res.pl = l.pl;
res.pr = min(M * 1LL, l.pr * 1LL * r.pp);
res.pp = min(M * 1LL, l.pp * 1LL * r.pp);
res.y = l.y;
}
}
return res;
}
void ubd(int tl, int tr, int x, int xx, int yy, int pos)
{
if (tl == tr)
{
t[pos] = ban(xx, yy);
return;
}
int m = (tl + tr) / 2;
if (x <= m)
ubd(tl, m, x, xx, yy, pos * 2);
else
ubd(m + 1, tr, x, xx, yy, pos * 2 + 1);
t[pos] = mer(t[pos * 2], t[pos * 2 + 1]);
}
int X[N], Y[N];
int init(int N_, int X[], int Y[])
{
n = N_;
for (int i = 0; i < n; ++i)
{
::X[i] = X[i];
::Y[i] = Y[i];
}
for (int i = 0; i < n; ++i)
ubd(0, n - 1, i, X[i], Y[i], 1);
return t[1].ans;
}
int updateX(int pos, int val)
{
X[pos] = val;
ubd(0, n - 1, pos, X[pos], Y[pos], 1);
return t[1].ans;
}
int updateY(int pos, int val)
{
Y[pos] = val;
ubd(0, n - 1, pos, X[pos], Y[pos], 1);
return t[1].ans;
}
