#include "horses.h"
#include <bits/stdc++.h>
#define L(n) (n << 1)
#define R(n) (n << 1 | 1)
#define MOD 1000000007LL
using namespace std;
int N;
int X[500005], Y[500005];
int treeX[2000000];
long long sumX[2000000];
int mxY[2000000];
int last, now;//product sum suffix skrg
int pointer;//posisi suffix skrg
int residue;//product sum % MOD prefix skrg
//segtree 2 buah dan 1 BIT nice
int kali(long long a, long long b) {
return a * b > 1000000000 ? 1000000001 : a * b;
}
//segtreeX
void buildX(int n, int l, int r) {
if(l == r) {
treeX[n] = X[l];
sumX[n] = X[l];
return;
}
int mid = (l + r) >> 1;
buildX(L(n), l, mid);
buildX(R(n), mid + 1, r);
treeX[n] = kali(treeX[L(n)], treeX[R(n)]);
}
void upX(int n, int l, int r, int pos, int val) {
if(l == r) {
treeX[n] = val;
sumX[n] = val;
return;
}
int mid = (l + r) >> 1;
if(pos <= mid) upX(L(n), l, mid, pos, val);
else upX(R(n), mid + 1, r, pos, val);
treeX[n] = kali(treeX[L(n)], treeX[R(n)]);
sumX[n] = sumX[L(n)] * sumX[R(n)] % MOD;
}
//query mencari suffix terpanjang yang product sumnya < sum suffix sekarang
void findposX(int n, int l, int r, long long need = last) {
// cout << l << " " << r << " " << need << "\n";
// cout << treeX[L(n)] << " " << treeX[R(n)] << "\n";
if(l == r) {
pointer = l;
return;
}
int mid = (l + r) >> 1;
if(treeX[R(n)] >= need) findposX(R(n), mid + 1, r, need);
else {
now *= treeX[R(n)];
need = ceil((double) need / treeX[R(n)]);
findposX(L(n), l, mid, need);
}
}
long long sum_queryX(int n, int l, int r, int pos) {
if(r <= pos) {
return sumX[n];
}
int mid = (l + r) >> 1;
long long res = sum_queryX(L(n), l, mid, pos);
if(pos > mid) res *= sum_queryX(R(n), mid + 1, r, pos);
return res % MOD;
}
void buildX() {buildX(1, 0, N);}
void upX(int pos, int val) {upX(1, 0, N, pos, val);}
void findposX() {findposX(1, 0, N);}
long long sum_queryX(int pos) {return pos >= 0 ? sum_queryX(1, 0, N, pos) : 1;}
//segtree X end
//segtree Y
void buildY(int n, int l, int r) {
if(l == r) {
mxY[n] = Y[l];
return;
}
int mid = (l + r) >> 1;
buildY(L(n), l, mid);
buildY(R(n), mid + 1, r);
mxY[n] = max(mxY[L(n)], mxY[R(n)]);
}
void upY(int n, int l, int r, int pos, int val) {
if(l == r) {
mxY[n] = val;
return;
}
int mid = (l + r) >> 1;
if(pos <= mid) upY(L(n), l, mid, pos, val);
else upY(R(n), mid + 1, r, pos, val);
mxY[n] = max(mxY[L(n)], mxY[R(n)]);
}
int rmqY(int n, int l, int r, int pos) {
if(pos <= l) return mxY[n];
int mid = (l + r) >> 1;
int res = 0;
if(pos <= mid) res = rmqY(L(n), l, mid, pos);
res = max(res, rmqY(R(n), mid + 1, r, pos));
return res;
}
void buildY() {buildY(1, 1, N);}
void upY(int pos, int val) {upY(1, 1, N, pos, val);}
int rmqY(int pos) {
if(pos > N) return 0;
return rmqY(1, 1, N, pos);
}
//segtree Y end
int solve() {
long long res = 1;
long long bef = 1;
long long sisa = 1;
last = treeX[1];
if(last != 1000000001) res = rmqY(1);
while(1) {
now = 1;
findposX();
bef *= last / now;
if(last == 1000000001) {
sisa = sum_queryX(pointer - 1);
// cout << pointer - 1 << "\n";
// cout << sisa << "\n";
}
res = max(res, bef * rmqY(pointer + 1));
// cout << "sum sebelumnya: " << last << "\n";
// cout << "sum sekarang: " << now << "\n";
// cout << "posisi skrg: " << pointer << "\n";
// cout << "bef: " << bef << "\n";
// cout << "best di array Y di range "<< pointer + 1 << " " << N << " : " << rmqY(pointer + 1) << "\n\n";
if(now == 1) break;
swap(now, last);
}
return (res % MOD * sisa % MOD);
}
int init(int n, int x[], int y[]) {
N = n;
for(int i = 0; i < N; i++) X[i] = x[i], Y[i + 1] = y[i];
X[N] = 1;
buildX();
buildY();
return solve();
}
int updateX(int pos, int val) {
upX(pos, val);
return solve();
}
int updateY(int pos, int val) {
upY(pos + 1, val);
return solve();
}
