#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
typedef long long ll;
const int MAXN = 5e5 + 10;
const ll MOD = 1e9 + 7;
ll X[MAXN], Y[MAXN];
inline ll mult(ll a, ll b) {return (a * b) % MOD;}
inline ll mult(ll a, ll b, ll c) {return (mult(a, b)*c) % MOD;}
ll exp(ll x, ll b)
{
if (b == 0) return 1LL;
if (b % 2) return mult(x, exp(x, b-1));
else return exp(mult(x, x), b/2);
}
int N;
struct node
{
ll prefX, sufX, y;
bool bigPref;
ll val;
node (ll PX = 0, ll SX = 0, ll YY = 0, bool BIG = false) : prefX(PX), sufX(SX), y(YY), bigPref(BIG) {val = mult(prefX, y);}
node operator+(node outro)
{
node resp;
if (outro.y >= y || outro.bigPref || outro.prefX >= y || (sufX * outro.prefX) >= y || (sufX * outro.prefX * outro.y) >= y)
resp = node( mult(prefX, sufX, outro.prefX), outro.sufX, outro.y, bigPref || outro.bigPref || (prefX * sufX) >= MOD || (prefX * sufX * outro.prefX) >= MOD );
else resp = node(prefX, mult(sufX, outro.prefX, outro.sufX), y, bigPref);
return resp;
}
} seg[4*MAXN];
void build(int pos, int ini, int fim)
{
if (ini == fim)
{
seg[pos] = node(X[ini], 1, Y[ini]);
return;
}
int m = (ini + fim) >> 1;
int e = 2*pos; int d = 2*pos + 1;
build(e, ini, m );
build(d, m+1, fim);
seg[pos] = seg[e] + seg[d];
}
void segUpdate(int pos, int ini, int fim, int id)
{
if (id < ini || id > fim) return;
if (ini == fim)
{
seg[pos] = node(X[ini], 1, Y[ini]);
return;
}
int m = (ini + fim) >> 1;
int e = 2*pos; int d = 2*pos + 1;
segUpdate(e, ini, m , id);
segUpdate(d, m+1, fim, id);
seg[pos] = seg[e] + seg[d];
}
int init(int _N, int _X[], int _Y[])
{
N = _N;
for (int i = 1; i <= N; i++) X[i] = _X[i-1], Y[i] = _Y[i-1];
build(1, 1, N);
return (int)seg[1].val;
}
int updateX(int id, int _val)
{
++id;
X[id] = _val;
segUpdate(1, 1, N, id);
return (int)seg[1].val;
}
int updateY(int id, int _val)
{
++id;
Y[id] = _val;
segUpdate(1, 1, N, id);
return (int)seg[1].val;
}
