#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 1e9+7;
const int N = 500100;
const ll MAX = 2000000000;
int n;
int tmx[N*4], a[N], b[N];
pair<int, int> t[N*4], ob[N*4];
void push(int v){
if (ob[v].first == 0)
return;
t[v+v] = t[v+v+1] = ob[v];
ob[v+v] = ob[v+v+1] = ob[v];
ob[v] = {0, 0};
}
pair<int, int> get(int v, int l, int r, int pos){
if (l == r){
return t[v];
}
int mid = (l+r)>>1;
push(v);
if (pos <= mid)
return get(v+v, l, mid, pos); else
return get(v+v+1, mid+1, r, pos);
}
void update(int v, int l, int r, int tl, int tr, pair<int, int> x){
if (l > r || tl > r || l > tr || tl > tr)
return;
if (tl <= l && r <= tr){
t[v] = x;
ob[v] = x;
return;
}
int mid = (l+r)>>1;
push(v);
update(v+v, l, mid, tl, tr, x);
update(v+v+1, mid+1, r, tl, tr, x);
}
void updatemx(int v, int l, int r, int pos, int x){
if (l == r){
tmx[v] = x;
return;
}
int mid = (l+r)>>1;
if (pos <= mid)
updatemx(v+v, l, mid, pos, x); else
updatemx(v+v+1, mid+1, r, pos, x);
tmx[v] = max(tmx[v+v], tmx[v+v+1]);
}
int getmx(int v, int l, int r, int tl, int tr){
if (l > r || tl > r || l > tr || tl > tr)
return 0;
if (tl <= l && r <= tr)
return tmx[v];
int mid = (l+r)>>1;
return max(getmx(v+v, l, mid, tl, tr), getmx(v+v+1, mid+1, r, tl, tr));
}
ld sumLog = 0;
ll mnzh = 1;
ll binpow(ll x, ll y){
ll res = 1;
while(y){
if (y & 1)
res = (res * x) % MOD;
y>>=1;
x = (x * x) % MOD;
}
return res;
}
int query(){
ll cur = 1;
ll curmnzh = mnzh;
ld mx = -1;
ll mxans = 0;
ld cursum = sumLog;
for (int i = n; i >= 1; i--){
if (a[i] == 1){
pair<int, int> pr = get(1, 1, n, i);
i = pr.first;
ll gt = getmx(1, 1, n, pr.first, pr.second);
if (cursum+log((ld)gt) > mx){
mx = cursum+log((ld)gt);
mxans = (curmnzh*gt)%MOD;
}
} else {
ll gt = b[i];
if (cursum+log((ld)gt) > mx){
mx = cursum+log((ld)gt);
mxans = (curmnzh*gt)%MOD;
}
}
//cout << curmnzh << ' ' << cursum << ' ' << cur << ' ' << b[i] << endl;
curmnzh = (curmnzh * binpow(a[i], MOD-2))%MOD;
cursum -= log((ld)a[i]);
cur *= a[i];
if (cur > MAX)
break;
}
return mxans;
}
int init(int N, int X[], int Y[]) {
n = N;
for (int i = 1; i <= n; i++){
a[i] = X[i-1];
b[i] = Y[i-1];
sumLog += log((ld)a[i]);
mnzh = (mnzh * a[i])%MOD;
updatemx(1, 1, n, i, b[i]);
if (a[i] == 1){
pair<int, int> pr = {i, i};
if (a[i-1] == 1)
pr.first = get(1, 1, n, i-1).first;
update(1, 1, n, pr.first, pr.second, pr);
}
}
return query();
}
int updateX(int pos, int val) {
++pos;
if (a[pos] == 1){
pair<int, int> pr = get(1, 1, n, pos);
update(1, 1, n, pr.first, pos-1, {pr.first, pos-1});
update(1, 1, n, pos+1, pr.second, {pos+1, pr.second});
}
mnzh = (mnzh*binpow(a[pos], MOD-2))%MOD;
sumLog -= log((ld)a[pos]);
a[pos] = val;
mnzh = (mnzh*a[pos])%MOD;
sumLog += log((ld)a[pos]);
if (a[pos] == 1){
pair<int, int> pr = {pos, pos};
if (a[pos-1] == 1)
pr.first = get(1, 1, n, pos-1).first;
if (a[pos+1] == 1)
pr.second = get(1, 1, n, pos+1).second;
update(1, 1, n, pr.first, pr.second, pr);
}
return query();
}
int updateY(int pos, int val) {
++pos;
b[pos] = val;
updatemx(1, 1, n, pos, val);
return query();
}
/**
3
2 1 3
3 4 1
1
2 1 2
*/
