#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i , j , k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define lid id<<1
#define rid lid|1
typedef long long ll;
typedef pair<ll ,ll> pll;
const int MOD = 1e9 + 7;
const int MAXN = 5e5 + 10;
int N;
ll A[MAXN], B[MAXN], segM[MAXN << 2], segX[MAXN << 2];
bool segH[MAXN << 2];
void build(int l = 0, int r = N, int id = 1) {
if (l == r - 1) {
segM[id] = A[l];
segX[id] = B[l];
segH[id] = segM[id] > 1;
return;
}
int mid = l +r >> 1;
build(l , mid , lid);
build(mid , r ,rid);
segM[id] = segM[lid] * segM[rid] % MOD;
segX[id] = max(segX[lid] , segX[rid]);
segH[id] = segH[lid] | segH[rid];
}
void segUpt(int pos , int l = 0 , int r = N, int id = 1) {
if (l == r - 1) {
segM[id] = A[l];
segX[id] = B[l];
segH[id] = segM[id] > 1;
return;
}
int mid = l +r >> 1;
if (pos < mid) segUpt(pos , l , mid , lid);
else segUpt(pos , mid , r ,rid);
segM[id] = segM[lid] * segM[rid] % MOD;
segX[id] = max(segX[lid] , segX[rid]);
segH[id] = segH[lid] | segH[rid];
}
int segRight(int lim , int l = 0, int r = N, int id = 1) {
if (l >= lim || !segH[id]) return -1;
if (l == r - 1) return l;
int mid = l + r >> 1;
int res = segRight(lim , mid , r, rid);
if (!~res) res = segRight(lim , l , mid, lid);
return res;
}
int segMax(int lim , int l = 0, int r = N, int id = 1) {
if (l >= lim) return segX[id];
int mid = l +r >> 1;
int res = segMax(lim , mid , r , rid);
if (lim < mid) res = max(res , segMax(lim , l , mid , lid));
return res;
}
int segMul(int lim , int l = 0, int r = N, int id = 1) {
if (l >= lim) return 1;
if (r <= lim) return segM[id];
int mid = l + r >> 1;
return 1ll * segMul(lim , l , mid , lid) * segMul(lim , mid , r, rid) % MOD;
}
int solve() {
vector<pll> pos;
ll mul = 1;
int last = N;
while (mul < 1e9 && last) {
int id = segRight(last);
if (!~id) {
pos.pb({0 , segMax(0)});
break;
}
mul *= B[id];
last = id;
pos.pb({id , segMax(id)});
}
ll best = 0;
bool biger = false;
for (auto e : pos) {
ll local = e.second;
if(biger)
local = best;
else if (best > local)
local = best;
local *= A[e.first];
if (local >= MOD) {
biger = true;
local %= MOD;
}
best = local;
}
//cout << best * segMul(pos.back().first) % MOD << endl;
return best * segMul(pos.back().first) % MOD;
}
int init(int N2, int X[], int Y[]) {
N = N2;
rep(i , 0 , N) {
A[i] = X[i];
B[i] = Y[i];
}
build();
return solve();
}
int updateX(int pos, int val) {
A[pos] = val;
segUpt(pos);
return solve();
}
int updateY(int pos, int val) {
B[pos] = val;
segUpt(pos);
return solve();
}
