#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 5e5;
const int MOD = 1e9 + 7;
struct AIB {
int aib[MAX_N + 1];
void init() {
for ( int i = 0; i <= MAX_N; i++ )
aib[i] = 1;
}
void update( int i, int x ) {
while ( i <= MAX_N ) {
aib[i] = (long long)aib[i] * x % MOD;
i += (i & -i);
}
}
int query( int i ) {
int p = 1;
while ( i > 0 ) {
p = (long long)p * aib[i] % MOD;
i -= (i & -i);
}
return p;
}
} horses;
struct info {
long double maxx, pos;
info operator + ( const info &x ) const {
if ( x.maxx > maxx )
return x;
return *this;
}
};
struct AINT {
int lst, rst;
info aint[4 * MAX_N];
long double lazy[4 * MAX_N];
void init( int l, int r ) {
lst = l;
rst = r;
}
void propag( int v, int l, int r ) {
if ( aint[v].pos == 0 )
aint[v].pos = l;
aint[v].maxx += lazy[v];
if ( l != r ) {
lazy[v * 2 + 1] += lazy[v];
lazy[v * 2 + 2] += lazy[v];
}
lazy[v] = 0;
}
void update( int v, int l, int r, int lu, int ru, long double x ) {
propag( v, l, r );
if ( l > ru || r < lu )
return;
if ( lu <= l && r <= ru ) {
lazy[v] += x;
propag( v, l, r );
return;
}
int mid = (l + r) / 2;
update( v * 2 + 1, l, mid, lu, ru, x );
update( v * 2 + 2, mid + 1, r, lu, ru, x );
aint[v] = aint[v * 2 + 1] + aint[v * 2 + 2];
}
void update( int l, int r, long double x ) {
update( 0, lst, rst, l, r, x );
}
info query( int v, int l, int r, int lq, int rq ) {
propag( v, l, r );
if ( l > rq || r < lq )
return { 0, 0 };
if ( lq <= l && r <= rq )
return aint[v];
int mid = (l + r) / 2;
info a = query( v * 2 + 1, l, mid, lq, rq );
info b = query( v * 2 + 2, mid + 1, r, lq, rq );
return a + b;
}
info query( int l, int r ) {
return query( 0, lst, rst, l, r );
}
} cost;
int lgPut( int a, int n ) {
if ( n == 0 )
return 1;
int p = lgPut( a, n / 2 );
p = (long long)p * p % MOD;
if ( n % 2 == 1 )
p = (long long)p * a % MOD;
return p;
}
int inv( int x ) {
return lgPut( x, MOD - 2 );
}
int n;
int x[MAX_N + 1], y[MAX_N + 1];
void calc() {
horses.init();
cost.init( 1, n );
for ( int i = 1; i <= n; i++ ) {
horses.update( i, x[i] );
cost.update( i, n, log( x[i] ) );
cost.update( i, i, log( y[i] ) );
}
}
int answer() {
int i = cost.query( 1, n ).pos;
return (long long)horses.query( i ) * y[i] % MOD;
}
int init( int N, int X[], int Y[] ) {
n = N;
for ( int i = n - 1; i >= 0; i-- )
x[i + 1] = X[i], y[i + 1] = Y[i];
calc();
printf( "\n\n" );
return answer();
}
int updateX( int pos, int val ) {
int i = pos + 1;
cost.update( i, n, -log( x[i] ) );
horses.update( i, inv( x[i] ) );
x[i] = val;
cost.update( i, n, log( x[i] ) );
horses.update( i, x[i] );
return answer();
}
int updateY( int pos, int val ) {
int i = pos + 1;
cost.update( i, i, -log( y[i] ) );
y[i] = val;
cost.update( i, i, log( y[i] ) );
return answer();
}
