#include "horses.h"
#include <bits/stdc++.h>
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
#define fora(i, a, b) for(int i = int(a); i >= int(b); -- i)
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int lim = 5e5;
bool stbool[4 * lim + 2];
int stmax[4 * lim + 2];
ll bit[lim + 2];
int n;
ll x[lim + 2];
int y[lim + 2];
int posicion[33];
ll valor[33];
int mayor[33];
int dif1 = 0;
ll expb(ll numero){
ll res = 1LL;
int aux = 1e9 + 5;
forn(i, 0, 29){
if(((1 << i) & aux)){
res *= numero;
res %= mod;
}
numero *= numero;
numero %= mod;
}
return res;
}
void initbool(int nodo, int l, int r){
if(l == r){
stbool[nodo] = (x[l] != 1);
return;
}
int mitad = (l + r) / 2;
initbool(nodo * 2, l, mitad);
initbool(nodo * 2 + 1, mitad + 1, r);
stbool[nodo] = stbool[nodo * 2] | stbool[nodo * 2 + 1];
}
int querybool(int nodo, int l, int r, int rango){
if(l > rango){
return 0;
}
if(!stbool[nodo]){
return 0;
}
if(l == r){
return l;
}
int mitad = (l + r) / 2, value;
value = querybool(nodo * 2 + 1, mitad + 1, r, rango);
if(!value){
value = querybool(nodo * 2, l, mitad, rango);
}
return value;
}
void updatebool(int nodo, int l, int r, int pos){
if(pos < l || pos > r){
return;
}
if(pos == l && pos == r){
stbool[nodo] ^= 1;
return;
}
int mitad = (l + r) / 2;
updatebool(nodo * 2, l, mitad, pos);
updatebool(nodo * 2, mitad + 1, r, pos);
stbool[nodo] = stbool[nodo * 2] | stbool[nodo * 2 + 1];
}
void initmax(int nodo, int l, int r){
if(l == r){
stmax[nodo] = y[l];
return;
}
int mitad = (l + r) / 2;
initmax(nodo * 2, l, mitad);
initmax(nodo * 2 + 1, mitad + 1, r);
stmax[nodo] = max(stmax[nodo * 2], stmax[nodo * 2 + 1]);
}
int querymax(int nodo, int l, int r, int li, int ls){
if(li > r || ls < l){
return 0;
}
if(li <= l && ls >= r){
return stmax[nodo];
}
int mitad = (l + r) / 2;
return max(querymax(nodo * 2, l, mitad, li, ls), querymax(nodo * 2 + 1, mitad + 1, r, li, ls));
}
void updatemax(int nodo, int l, int r, int pos, int val){
if(pos < l || pos > r){
return;
}
if(pos == l && pos == r){
stmax[nodo] = val;
return;
}
int mitad = (l + r) / 2;
updatemax(nodo * 2, l, mitad, pos, val);
updatemax(nodo * 2 + 1, mitad + 1, r, pos, val);
stmax[nodo] = max(stmax[nodo * 2], stmax[nodo * 2 + 1]);
}
void updatebit(int pos, ll valor){
for(int i = pos; i <= n; i += i & -i){
bit[i] *= valor;
bit[i] %= mod;
}
}
ll querybit(int pos){
ll res = 1LL;
for(int i = pos; i >= 1; i -= i & -i){
res *= bit[i];
res %= mod;
}
return res;
}
ll respuesta(){
int indice = 1;
ll auxiliar = 1LL, res;
if(n < 30){
forn(i, 2, n){
auxiliar *= x[i];
if(auxiliar < (ll) y[indice]){
auxiliar *= (ll) y[i];
}
if(auxiliar >= (ll) y[indice]){
indice = i;
auxiliar = 1LL;
}
else{
auxiliar /= (ll) y[i];
}
}
res = querybit(indice);
res *= (ll) y[indice];
res %= mod;
}
else{
forn(i, 2, 30){
auxiliar *= valor[i];
if(auxiliar < (ll) mayor[indice] && mayor[i]){
auxiliar *= (ll) mayor[i];
}
if(auxiliar >= (ll) mayor[indice]){
auxiliar = 1LL;
indice = i;
}
else if(mayor[i]){
auxiliar /= (ll) mayor[i];
}
}
res = (valor[indice] == 1LL) ? 1LL : querybit(posicion[indice]);
res *= (ll) mayor[indice];
res %= mod;
}
return res;
}
int init(int N, int X[], int Y[]) {
n = N;
forn(i, 0, n - 1){
x[i + 1] = (ll) X[i];
y[i + 1] = Y[i];
bit[i + 1] = 1;
}
initbool(1, 1, n);
initmax(1, 1, n);
forn(i, 1, n){
if(x[i] != 1){
updatebit(i, x[i]);
dif1 ++;
}
}
posicion[31] = n + 1;
ll res;
if(n >= 30){
fora(i, 30, max(1, 31 - dif1)){
posicion[i] = querybool(1, 1, n, posicion[i + 1] - 1);
valor[i] = x[posicion[i]];
mayor[i] = querymax(1, 1, n, posicion[i], posicion[i + 1] - 1);
}
fora(i, max(1, 31 - dif1) - 1, 1){
posicion[i] = 0;
valor[i] = 1LL;
if(posicion[i + 1]){
mayor[i] = querymax(1, 1, n, 1, posicion[i + 1] - 1);
}
else{
mayor[i] = mayor[i + 1];
}
}
}
/**forn(i, 1, 30){
cout << posicion[i] << " " << mayor[i] << " " << valor[i] << "\n";
}*/
res = respuesta();
return (int) res;
}
int updateX(int pos, int val) {
ll actualiza = x[pos + 1];
if(val != (ll) actualiza){
actualiza = expb(actualiza);
actualiza *= (ll) val;
actualiza %= mod;
updatebit(pos + 1, actualiza);
if(val == 1){
updatebool(1, 1, n, pos + 1);
dif1 --;
}
if(val > 1 && x[pos + 1] == 1){
updatebool(1, 1, n, pos + 1);
dif1 ++;
}
if(n >= 30){
if(val == 1){
if(pos + 1 > posicion[1]){
forn(i, 2, 30){
if(posicion[i] == pos + 1){
posicion[i] = posicion[i - 1];
mayor[i] = max(mayor[i], mayor[i - 1]);
valor[i] = valor[i - 1];
fora(j, i - 1, 2){
posicion[i] = posicion[i - 1];
mayor[i] = mayor[i - 1];
valor[i] = valor[i - 1];
}
break;
}
}
}
if(pos + 1 >= posicion[1]){
if(dif1 >= 30){
posicion[1] = querybool(1, 1, n, posicion[2] - 1);
mayor[1] = querymax(1, 1, n, posicion[1], posicion[2] - 1);
valor[1] = x[posicion[1]];
}
else{
posicion[1] = 0;
mayor[1] = querymax(1, 1, n, 1, posicion[31 - dif1] - 1);
valor[1] = 1LL;
}
}
}
else if(x[pos + 1] > 1 && posicion[1] <= pos + 1){
forn(i, 1, 30){
if(posicion[i] == pos + 1){
valor[i] = (ll) val;
break;
}
}
}
else if(x[pos + 1] == 1 && posicion[1] < pos + 1){
forn(i, 1, 30){
if(posicion[i + 1] > pos + 1){
posicion[i] = pos + 1;
valor[i] = (ll) val;
mayor[i] = querymax(1, 1, n, pos + 1, posicion[i + 1] - 1);
if(i != 1){
if(posicion[i - 1] == 0){
mayor[i - 1] = querymax(1, 1, n, 1, pos);
fora(j, i - 2, 1){
mayor[j] = mayor[j + 1];
}
}
else{
mayor[i - 1] = querymax(1, 1, n, posicion[i - 1], pos);
}
}
break;
}
else{
posicion[i] = posicion[i + 1];
mayor[i] = mayor[i + 1];
valor[i] = valor[i + 1];
}
}
}
}
x[pos + 1] = val;
/**forn(i, 1, 30){
cout << posicion[i] << " " << mayor[i] << " " << valor[i] << "\n";
}*/
}
ll res = respuesta();
return (int) res;
}
int updateY(int pos, int val) {
updatemax(1, 1, n, pos + 1, val);
y[pos + 1] = val;
if(n >= 30){
fora(i, 30, 1){
if(pos + 1 >= posicion[i]){
mayor[i] = querymax(1, 1, n, (posicion[i] == 0) ? 1 : posicion[i], posicion[i + 1] - 1);
break;
}
}
/**forn(i, 1, 30){
cout << posicion[i] << " " << mayor[i] << " " << valor[i] << "\n";
}*/
}
ll res = respuesta();
return (int) res;
}
