#include "horses.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define int long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 100000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod = 1000000007 ;
const int mod1 = 998244353 ;
const int N = 7e5 + 10 ;
const int MAXN = 1e9 + 10 ;
mt19937 R(time(0));
map < int , int > ma , ma1 ;
int nodex[ 4 * N ] ;
pair < int , int > nodey[ 4 * N ] ;
int x[ N ] , y[ N ] ;
void buildx( int v , int vl , int vr ){
if( vl == vr ){
nodex[ v ] = x[ vl - 1 ] ;
return ;
}
int vm = ( vl + vr ) / 2 ;
buildx( v + v , vl , vm ) ;
buildx( v + v + 1 , vm + 1 , vr ) ;
nodex[ v ] = ( nodex[ v + v ] * nodex[ v + v + 1 ] ) % mod ;
return ;
}
void updatex( int v , int vl , int vr , int pos , int val ){
if( vl == vr ){
nodex[ v ] = val ;
x[ pos - 1 ] = val ;
return ;
}
int vm = ( vl + vr ) / 2 ;
if( vm >= pos )updatex( v + v , vl , vm , pos , val ) ;
else updatex( v + v + 1 , vm + 1 , vr , pos , val ) ;
nodex[ v ] = ( nodex[ v + v ] * nodex[ v + v + 1 ] ) % mod ;
return ;
}
int getx( int v , int vl , int vr , int l , int r ){
if( l > r ) return 1 ;
if( vl == l && vr == r ){
return nodex[ v ] ;
}
int vm = ( vl + vr ) / 2 ;
int a = getx( v + v , vl , vm , l , min( r , vm ) ) ;
int b = getx( v + v + 1 , vm + 1 , vr , max( vm + 1 , l ) , r ) ;
return ( a * b ) % mod ;
}
// for y
void buildy( int v , int vl , int vr ){
if( vl == vr ){
nodey[ v ] = { y[ vl - 1 ] , vl - 1 } ;
return ;
}
int vm = ( vl + vr ) / 2 ;
buildy( v + v , vl , vm ) ;
buildy( v + v + 1 , vm + 1 , vr ) ;
nodey[ v ] = max( nodey[ v + v ] , nodey[ v + v + 1 ] ) ;
return ;
}
void updatey( int v , int vl , int vr , int pos , int val ){
if( vl == vr ){
nodey[ v ] = { val , vl - 1 } ;
y[ vl - 1 ] = val ;
return ;
}
int vm = ( vl + vr ) / 2 ;
if( vm >= pos ) updatey( v + v , vl , vm , pos , val ) ;
else updatey( v + v + 1 , vm + 1 , vr , pos , val ) ;
nodey[ v ] = max( nodey[ v + v ] , nodey[ v + v + 1 ] ) ;
return ;
}
pair < int , int > gety( int v , int vl , int vr , int l , int r ){
if( l > r ) return { 0 , 0 } ;
if( vl == l && vr == r ){
return nodey[ v ] ;
}
int vm = ( vl + vr ) / 2 ;
pair < int , int > a = gety( v + v , vl , vm , l , min( r , vm ) ) ;
pair < int , int > b = gety( v + v + 1 , vm + 1 , vr , max( vm + 1 , l ) , r ) ;
return max( a , b ) ;
}
int n ;
set < int > se ;
int pas(){
int ans = 1 ;
int mx = 0 , lst = n ;
int is_ok = n - 1 ;
for( auto yy : se ){
int X = -yy ;
pair < int , int > p = { 0 , 0 } ;
int l = X + 2 , r = lst ;
p = gety( 1 , 1 , n , l , r ) ;
if( p.f > mx ){
is_ok = p.s ;
}
mx = max( mx , p.f ) ;
if( X == -1 ) break ;
if( y[ X ] > mx ){
is_ok = X ;
}
mx = max( mx , y[ X ] ) ;
mx = mx * x[ X ] ;
if( mx > MAXN ) break ;
lst = X ;
}
ans = y[ is_ok ] * getx( 1 , 1 , n , 1 , is_ok + 1 ) ;
ans %= mod ;
return ans ;
}
signed init(signed N, signed X[], signed Y[]){
FOR( i , N ) x[ i ] = X[ i ] , y[ i ] = Y[ i ] ;
n = N ;
se.insert( 1 ) ;
FOR( i , N ){
if( x[ i ] != 1 ) se.insert( - i ) ;
}
buildx( 1 , 1 , n ) ;
buildy( 1 , 1 , n ) ;
return pas() ;
}
signed updateX(signed pos, signed val){
if( x[ pos ] != 1 ){
se.erase( se.find( - pos ) ) ;
}
if( val != 1 ) se.insert( - pos ) ;
updatex( 1 , 1 , n , pos + 1 , val ) ;
return pas() ;
}
signed updateY(signed pos, signed val){
updatey( 1 , 1 , n , pos + 1 , val ) ;
return pas() ;
}
//static char buffer[1024];
//static int currentChar = 0;
//static int charsNumber = 0;
//
//signed main() {
// signed N;
// cin >> N ;
//
// signed *X = (signed *)malloc(sizeof(int) * (unsigned int)N);
// signed *Y = (signed *)malloc(sizeof(int) * (unsigned int)N);
//
// for (int i = 0; i < N; i++) {
// cin >> X[ i ] ;
// }
//
// for (int i = 0; i < N; i++) {
// cin >> Y[ i ] ;
// }
//
// printf("%d\n", init(N, X, Y));
//
// int M;
// cin >> M ;
//
// for (int i = 0; i < M; i++) {
// int type;
// cin >> type ;
// int pos;
// cin >> pos ;
// int val;
// cin >> val ;
//
// if (type == 1) {
// printf("%d\n", updateX(pos, val));
// } else if (type == 2) {
// printf("%d\n", updateY(pos, val));
// }
// }
//
// return 0;
//}
