#include "horses.h"
#include<bits/stdc++.h>
#define MAX 500005
#define MOD 1000000007
#define mid (l+r)/2
#define optimiza_io cin.tie(0); ios_base::sync_with_stdio(0);
using namespace std;
typedef long long i64;
struct node
{
double sum;
i64 mult;
double bestsum;
i64 bestmult;
};
node tree[8*MAX];
i64 xx[MAX];
i64 yy[MAX];
int gN;
void unite( int x , int l , int r )
{
tree[x].sum = tree[l].sum + tree[r].sum;
tree[x].mult = ( tree[l].mult * tree[r].mult ) % MOD;
if( tree[l].bestsum > tree[l].sum + tree[r].bestsum )
{
tree[x].bestsum = tree[l].bestsum;
tree[x].bestmult = tree[l].bestmult;
}
else
{
tree[x].bestsum = tree[l].sum + tree[r].bestsum;
tree[x].bestmult = ( tree[l].mult * tree[r].bestmult ) % MOD;
}
}
void initTree( int x , int l , int r )
{
if( l == r )
{
tree[x].sum = log10( xx[l] );
tree[x].mult = xx[l] % MOD;
tree[x].bestsum = tree[x].sum + log10( yy[l] );
tree[x].bestmult = ( tree[x].mult * yy[l] ) % MOD;
return;
}
initTree( 2*x+1 , l , mid );
initTree( 2*x+2 , mid+1 , r );
unite( x , 2*x+1 , 2*x+2 );
}
int init(int N, int X[], int Y[]) {
gN = N;
for( i64 i = 0; i < N; i ++ )
xx[i] = X[i];
for( i64 i = 0; i < N; i ++ )
yy[i] = Y[i];
initTree( 0 , 0 , N - 1 );
return ( int ) tree[0].bestmult;
}
void upd( int x , int l , int r , int q , int v , bool t )
{
if( l > q or r < q )
return;
if( l == r )
{
if( ! t )
xx[l] = v;
else
yy[l] = v;
tree[x].sum = log10( xx[l] );
tree[x].mult = xx[l] % MOD;
tree[x].bestsum = tree[x].sum + log10( yy[l] );
tree[x].bestmult = ( tree[x].mult * yy[l] ) % MOD;
return;
}
upd( 2*x+1 , l , mid , q , v , t );
upd( 2*x+2 , mid+1 , r , q , v , t );
unite( x , 2*x+1 , 2*x+2 );
}
int updateX(int pos, int val) {
upd( 0 , 0 , gN - 1 , pos , val , 0 );
return ( int ) tree[0].bestmult;
}
int updateY(int pos, int val) {
upd( 0 , 0 , gN - 1 , pos , val , 1 );
return ( int ) tree[0].bestmult;
}
