#include "horses.h"
#include <bits/stdc++.h>
#define optimiza_io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pb push_back
#define ft first
#define sd second
#define ll long long
#define ld long double
#define ull unsigned long long
using namespace std;
const ll maxn = 500050, mod = 1000000007ll;
ll n;
ll x[maxn],y[maxn];
ll stprod[8*maxn]; //-1ll es overflow, sino, es normal
ll stmax[8*maxn];
ll stmodded[8*maxn];
void build1( ll nodo, ll ini, ll fin )
{
if( ini == fin )
{
stprod[nodo] = x[ini];
stmodded[nodo] = x[ini]%mod;
return;
}
ll md = (ini+fin)/2;
build1( 2*nodo+1, ini, md );
build1( 2*nodo+2, md+1, fin );
if( stprod[2*nodo+1] == -1ll || stprod[2*nodo+2] == -1ll )
stprod[nodo] = -1ll;
else if( ((ld)stprod[2*nodo+1]) >= (((ld)1000000000.0) / ((ld)stprod[2*nodo+2])) ) //habrá overflow
stprod[nodo] = -1ll;
else
stprod[nodo] = stprod[2*nodo+1] * stprod[2*nodo+2];
stmodded[nodo] = (stmodded[2*nodo+1] * stmodded[2*nodo+2])%mod;
return;
}
ll getprod( ll nodo, ll ini, ll fin, ll sq, ll eq ) // -1ll
{
if( ini > eq || fin < sq ){
return 1ll;
}
if( ini >= sq && fin <= eq )
{
stmodded[nodo] = x[ini];
if( stprod[nodo] == -1ll )
return -1ll;
return stprod[nodo];
}
ll md = (ini+fin)/2;
ll izq = getprod( 2*nodo+1, ini, md, sq, eq );
ll der = getprod( 2*nodo+2, md+1, fin, sq, eq );
if( izq == -1ll || der == -1ll ) return -1ll;
if( ((ld)izq) >= (((ld)1000000000.0) / ((ld)der)) ) return -1ll;
return izq*der;
}
ll getprod2( ll nodo, ll ini, ll fin, ll sq, ll eq )
{
if( ini > eq || fin < sq ) return 1ll;
if( ini >= sq && fin <= eq ) return stmodded[nodo];
ll md = (ini+fin)/2;
return ( getprod( 2*nodo+1, ini, md, sq, eq ) * getprod( 2*nodo+2, md+1, fin, sq, eq ) )%mod;
}
void upd_max( ll nodo )
{
ll right_prod = getprod( 0, 0, n-1, stmax[2*nodo+1] + 1, stmax[2*nodo+2] );
if( ((ld)right_prod) >= (((ld)1000000000.0) / ((ld)y[stmax[2*nodo+2]]) ) )
right_prod = -1ll;
else
right_prod *= y[stmax[2*nodo+2]];
if(right_prod == -1ll || right_prod > y[stmax[2*nodo+1]] )
stmax[nodo] = stmax[2*nodo+2];
else
stmax[nodo] = stmax[2*nodo+1];
return;
}
void build2( ll nodo, ll ini, ll fin )
{
if( ini == fin )
{
stmax[nodo] = ini;
return;
}
ll md = (ini+fin)/2;
build2( 2*nodo+1, ini, md );
build2( 2*nodo+2, md+1, fin );
upd_max(nodo);
return;
}
void upd_y( ll nodo, ll ini, ll fin, ll p )
{
if( ini > p || fin < p ) return;
if( ini == fin ){
assert( ini == p );
return;
}
ll md = (ini+fin)/2;
upd_y( 2*nodo+1, ini, md, p );
upd_y( 2*nodo+2, md+1, fin, p );
upd_max( nodo );
return;
}
void upd_prod( ll nodo, ll ini, ll fin, ll p )
{
if( ini > p || fin < p ) return;
if( ini == fin )
{
assert( ini == p );
stprod[nodo] = x[ini];
stmodded[nodo] = x[ini]%mod;
return;
}
ll md = (ini+fin)/2;
upd_prod( 2*nodo+1, ini, md, p );
upd_prod( 2*nodo+2, md+1, fin, p );
upd_max( nodo );
if( stprod[2*nodo+1] == -1ll || stprod[2*nodo+2] == -1ll )
stprod[nodo] = -1ll;
else if( ((ld)stprod[2*nodo+1]) >= (((ld)1000000000.0) / ((ld)stprod[2*nodo+2])) ) //habrá overflow
stprod[nodo] = -1ll;
else
stprod[nodo] = stprod[2*nodo+1] * stprod[2*nodo+2];
stmodded[nodo] = (stmodded[2*nodo+1] * stmodded[2*nodo+2])%mod;
return;
}
int init(int N, int X[], int Y[]) {
n = (ll)N;
for( ll i=0; i<N; i++ ){
x[i] = (ll)X[i];
y[i] = (ll)Y[i];
}
build1( 0, 0, n-1 );
build2( 0, 0, n-1 );
return (int)((getprod2( 0, 0, n-1, 0, stmax[0])*y[stmax[0]])%mod);
}
int updateX(int pos, int val) {
x[pos] = ((ll)val);
upd_prod( 0, 0, n-1, pos );
return (int)((getprod2( 0, 0, n-1, 0, stmax[0])*y[stmax[0]])%mod);
}
int updateY(int pos, int val) {
y[pos] = ((ll)val);
upd_y( 0, 0, n-1, pos );
return (int)((getprod2( 0, 0, n-1, 0, stmax[0])*y[stmax[0]])%mod);
}
