#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
const int MAXN = 500100;
const ll MOD = 1e9+7;
int n;
ll x[MAXN], y[MAXN];
ll tree3[4*MAXN];
void updPref (int p, ll val, int id = 1, int le = 1, int ri = n) {
if (le == ri){
tree3[id] = val;
return;
}
int mid = (le+ri)/2;
if (p <= mid)
updPref(p, val, 2*id, le, mid);
else
updPref(p, val, 2*id+1, mid+1, ri);
tree3[id] = (tree3[2*id] * tree3[2*id+1])%MOD;
}
ll prefX (int fr, int to, int id = 1, int le = 1, int ri = n) {
if (fr > ri || to < le) return 1;
if (fr <= le && ri <= to) return tree3[id];
int mid = (le+ri)/2;
return (prefX(fr, to, 2*id, le, mid) * prefX(fr, to, 2*id+1, mid+1, ri))%MOD;
}
ll prefX (int p) {
return prefX(1, p);
}
ll tree2[4*MAXN];
void upd2 (int p, ll val, int id = 1, int le = 1, int ri = n) {
if (le == ri){
tree2[id] = val;
return;
}
int mid = (le+ri)/2;
if (p <= mid)
upd2(p, val, 2*id, le, mid);
else
upd2(p, val, 2*id+1, mid+1, ri);
tree2[id] = tree2[2*id] + tree2[2*id+1];
}
ll get2 (int fr, int to, int id = 1, int le = 1, int ri = n) {
if (fr > ri || to < le) return 0;
if (fr <= le && ri <= to) return tree2[id];
int mid = (le+ri)/2;
return get2(fr, to, 2*id, le, mid) + get2(fr, to, 2*id+1, mid+1, ri);
}
ll get2 (int p) {
return get2(1, p);
}
int getId (ll sum, int id = 1, int le = 1, int ri = n) {
if (le == ri) return le;
int mid = (le+ri)/2;
if (sum <= tree2[2*id]) return getId(sum, 2*id, le, mid);
else return getId(sum-tree2[2*id], 2*id+1, mid+1, ri);
}
ll tree[4*MAXN];
void updTree (int p, ll val, int id = 1, int le = 1, int ri = n) {
if (le == ri){
tree[id] = le;
return;
}
int mid = (le+ri)/2;
if (p <= mid)
updTree(p, val, 2*id, le, mid);
else
updTree(p, val, 2*id+1, mid+1, ri);
if (y[tree[2*id]] > y[tree[2*id+1]])
tree[id] = tree[2*id];
else
tree[id] = tree[2*id+1];
}
ll getMaxY (int fr, int to, int id = 1, int le = 1, int ri = n) {
if (fr > ri || to < le) return 0;
if (fr <= le && ri <= to) return tree[id];
int mid = (le+ri)/2;
ll id1 = getMaxY(fr, to, 2*id, le, mid);
ll id2 = getMaxY(fr, to, 2*id+1, mid+1, ri);
if (y[id1] > y[id2]) return id1;
else return id2;
}
void print (){
FOR(i, 1, n) {
cout << " i = " << i << endl;
cout << " x = " << x[i] << " y = " << y[i] << endl;
cout << " prefX = " << prefX(i) << endl;
cout << " get2 pref = " << get2(i) << " get2 i = " << get2(i,i) << endl;
cout << " maxY i = " << getMaxY(i, i) << " getMaxY pref = " << getMaxY(1, i) << endl;
}
}
ll getMax () {
int id = 1;
ll tot = get2(1,n);
if (tot > 35) {
id = getId(tot-32);
}
ll cr = 1;
FOR(i, id+1, n) {
//cout << " i = " << i << " id = " << id << endl;
if (x[i] > 1) {
cr *= x[i];
if (cr * y[i] > y[id]) {
id = i;
cr = 1;
}
//cout << " case xi > 1, id = " << id << endl;
} else {
int le = i;
if (get2(le,n) == 0) le = n;
else {
ll sm = (i > 1) ? get2(1, i-1) : 0;
sm++;
le = getId(sm)-1;
}
/// [i;le] all x are equal to 1
int mxId = getMaxY(i, le);
// cout << " case xi = 1, le = " << le << endl;
if (cr * y[mxId] > y[id]) {
id = mxId;
cr = 1;
}
i = le;
// cout << " id = " << id << " i = " << i << endl;
}
}
//cout << " final id = " << id << endl;
ll ret = (prefX(id) * y[id])%MOD;
//cout << " prefX = " << prefX(id) << " y = " << y[id] << endl;
//print();
return ret;
}
int init(int N, int X[], int Y[]) {
n = N;
FOR(i, 1, n) x[i] = X[i-1];
FOR(i, 1, n) y[i] = Y[i-1];
// FOR(i, 0, MAXN-1) fen[i] = 1;
FOR(i, 1, n) updPref (i, x[i]);
FOR(i, 1, n) upd2(i, (x[i] > 1));
FOR(i, 1, n) updTree(i, y[i]);
return getMax();
}
int updateX(int pos, int val) {
pos++;
//updPref (pos, modInv(x[pos]));
//if (x[pos] > 1) upd2(pos, -1);
x[pos] = val;
updPref (pos, x[pos]);
//if (x[pos] > 1) upd2(pos, 1);
upd2(pos, (x[pos] > 1));
return getMax();
}
int updateY(int pos, int val) {
pos++;
y[pos] = val;
updTree(pos, y[pos]);
return getMax();
}
/*
3
2 1 3
3 4 1
1
2 1 2
ans: 8 6
10
2 1 1 1 1 2 1 1 1 1
4 5 6 1 4 5 6 1 100 1
0
ans: 400
*/
