#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];
struct node
{
ll k, x;
ll val;
ll lzK = 1, lzX = -1;
node(ll K = 0, ll X = 0) {k = K; x = X; val = ((k * x) % MOD);}
node operator+(node outro)
{
if (val > outro.val) return *this;
return outro;
}
} seg[4*MAXN];
int N;
ll exp(ll x, ll y)
{
if (y == 0) return 1;
if (y == 1) return x;
if (y % 2) return ((x * exp(x, y-1)) % MOD);
else
{
int aux = exp(x, (y / 2));
return ((aux * aux) % MOD);
}
}
void refreshK(int pos, int ini, int fim)
{
if (seg[pos].lzK == 1) return;
seg[pos].k = ((seg[pos].k * seg[pos].lzK) % MOD);
seg[pos].val = ((seg[pos].x * seg[pos].k) % MOD);
if (ini != fim)
{
int e = 2*pos; int d = 2*pos + 1;
seg[e].lzK *= seg[pos].lzK; seg[e].lzK %= MOD;
seg[d].lzK *= seg[pos].lzK; seg[d].lzK %= MOD;
}
seg[pos].lzK = 1;
}
void refreshX(int pos, int ini, int fim)
{
if (seg[pos].lzX == -1) return;
seg[pos].x = seg[pos].lzX;
seg[pos].val = ((seg[pos].k * seg[pos].x) % MOD);
//Nesse caso, sempre temos que ini == fim
seg[pos].lzX = -1;
}
void refresh(int pos, int ini, int fim)
{
refreshK(pos, ini, fim);
refreshX(pos, ini, fim);
}
void update(int pos, int ini, int fim, int p, int q, int valK, int valX)
{
refresh(pos, ini, fim);
if (q < ini || p > fim) return;
if (p <= ini && fim <= q)
{
if (valX == -1) seg[pos].lzK = valK;
else seg[pos].lzX = valX;
refresh(pos, ini, fim);
return;
}
int m = (ini + fim) >> 1;
int e = 2*pos; int d = 2*pos + 1;
update(e, ini, m, p, q, valK, valX);
update(d, m+1, fim, p, q, valK, valX);
seg[pos] = seg[e] + seg[d];
}
void build(int pos, int ini, int fim)
{
if (ini == fim)
{
seg[pos] = node(X[ini], 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];
}
int init(int _N, int _X[], int _Y[])
{
N = _N;
X[0] = 1;
for (int i = 1; i <= N; i++) {X[i] = (((long long)(_X[i-1]) * X[i-1]) % MOD); Y[i] = _Y[i-1];}
build(1, 1, N);
return (int)(seg[1].val);
}
int updateX(int id, int val)
{
id++;
update(1, 1, N, id, N, ((exp(X[id], (MOD-2)) * val) % MOD), -1);
X[id] = val;
return (int)(seg[1].val);
}
int updateY(int id, int val)
{
id++;
update(1, 1, N, id, id, 1, val);
Y[id] = val;
return (int)(seg[1].val);
}
