#define local
#ifndef local
#include "horses.h"
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<ll, ll> ii;
typedef pair<ii, ll> iii;
typedef pair<ii, ii> iiii;

const ll N = 3e5 + 5;

const ll oo = 1e18 + 7, mod = 1e9 + 7;

mt19937 rng(1);

ll rnd(ll l, ll r){
	ll temp = rng() % (r - l + 1);
	return abs(temp) + l;
}

ll n;
ll x[N], y[N];

ll tol[N << 2], maxi[N << 2];
 
ll get1[35], get2[35];

void upd(ll id, ll l, ll r, ll pos, ll val, ll type){
	if(l == r){
		if(type == 1) tol[id] = (x[pos] > 1);
		else maxi[id] = val;
		return;
	}
	ll mid = (l + r) >> 1;
	if(pos <= mid) upd(id << 1, l, mid, pos, val, type);
	else upd(id << 1 | 1, mid + 1, r, pos, val, type);
	tol[id] = tol[id << 1] + tol[id << 1 | 1];
	maxi[id] = max(maxi[id << 1], maxi[id << 1 | 1]);
}

ll get_pos(ll id, ll l, ll r, ll cnt){
	if(l == r){
		if(tol[id] < cnt) return -1;
		return l;
	}
	ll mid = (l + r) >> 1;
	if(tol[id << 1 | 1] >= cnt) return get_pos(id << 1 | 1, mid + 1, r, cnt);
	else return get_pos(id << 1, l, mid, cnt - tol[id << 1 | 1]);
}

ll maxii(ll id, ll l, ll r, ll L, ll R){
	if(l > R || r < L) return -oo;
	if(l >= L && r <= R) return maxi[id];                                 
	ll mid = (l + r) >> 1;
	return max(maxii(id << 1, l, mid, L, R), maxii(id << 1 | 1, mid + 1, r, L, R));
}

ll binpw(ll base, ll pw){
	ll ans = 1;
	while(pw){
		if(pw & 1) ans = (ans * base) % mod;
		base = (base * base) % mod;
		pw >>= 1;
	}
	return ans;
}

ll total = 1;

ll cal(){
	ll cnt = 0, lst_pos = n + 1, tol = 1;
	while(1){
		cnt++;
		ll temp = get_pos(1, 0, n - 1, cnt);
		//if(temp < 0) break;
		temp = max(temp, 0LL);
		get1[cnt] = x[temp], get2[cnt] = maxii(1, 0, n - 1, temp, lst_pos - 1);
		lst_pos = temp;
		tol *= x[temp];
		if(!temp) break;
		if(tol > 1e9) break;
	}
	if(tol > 1e9){
		tol /= get1[cnt];
		cnt--;
	}
	ii mx = {-1, -1};
	ll num1 = tol;
	for(ll i = 1; i <= cnt; i++){
		mx = max(mx, {num1 * get2[i], i});
		num1 /= get1[i];
	}
	//cout << total << " " << tol << " " << mx.fi << "\n";
	ll temp = (total * binpw(tol, mod - 2)) % mod;
	temp = (temp * mx.fi) % mod;
	return temp;
}

int init(int N, int X[], int Y[]) {
	n = N;
	for(ll i = 0; i < n; i++) x[i] = X[i];
	for(ll i = 0; i < n; i++) y[i] = Y[i];
	for(ll i = 0; i < n; i++) upd(1, 0, n - 1, i, x[i], 1);
	for(ll i = 0; i < n; i++) upd(1, 0, n - 1, i, y[i], 2);
	for(ll i = 0; i < n; i++) total = (total * x[i]) % mod;
	return (int)cal();
}

int updateX(int pos, int val) {	
	total = (total * binpw(x[pos], mod - 2)) % mod;
	total = (total * val) % mod;
	x[pos] = val;
	upd(1, 0, n - 1, pos, val, 1);
	//update1(pos, val);
	return cal();
}

int updateY(int pos, int val) {
	y[pos] = val;
	upd(1, 0, n - 1, pos, val, 2);
	//update2(pos, val);
	return cal();
}

/*
#ifdef local
void process(){
	ll n;
	cin >> n;
	int x[n], y[n];
	for(ll i = 0; i < n; i++) cin >> x[i];
	for(ll i = 0; i < n; i++) cin >> y[i];
	cout << init(n, x, y) << "\n";
	ll m;
	cin >> m;
	while(m--){
		ll a, b, c;
		cin >> a >> b >> c;
		if(a == 1) cout << updateX(b, c) << "\n";
		else cout << updateY(b, c) << "\n";
	}
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	process();
}
#endif
*/