#include<bits/stdc++.h>
#include "horses.h"
using namespace std;
#define pii pair<int,int>
#define int long long
int mod = 1e9+7;
const int STEPS = 30;
int exp(int a, int k){
if(k == 0) return 1;
int res = exp(a,k/2);
if(k % 2 == 0){
return (res*res)%mod;
}else{
return ((res*a%mod)*res)%mod;
}
}
int inv(int a){
return exp(a,mod-2);
}
struct Node{
int prod = 1;
int large = 0;
Node(){}
Node(int v){
prod = v;
large = v > 1;
}
Node(int p, int l){
prod = p;
large = l;
}
};
Node comb(Node a, Node b){
return Node(a.prod*b.prod%mod,a.large+b.large);
}
struct SegmentTree{
int len = 1;
vector<Node> S;
SegmentTree(){}
SegmentTree(int n){
while(len < n) len <<= 1;
S.resize(2*len);
}
Node query(int ql, int qr, int l= 0, int r = -2, int i = 1){
if(r == -2) r = len;
if(ql <= l && r <= qr) return S[i];
if(r <= ql || qr <= l) return 1;
int mid = (l+r)/2;
return comb(query(ql,qr,l,mid,i*2), query(ql,qr,mid,r,i*2+1));
}
void upd(int i, int v){
i += len;
S[i] = v;
for(i /= 2; i > 0; i /= 2){
S[i] = comb(S[i*2], S[i*2+1]);
}
}
};
struct SegmentTreeMax{
vector<int> S;
int len = 1;
SegmentTreeMax(int n){
while(len < n) len <<= 1;
S.resize(2*len);
}
SegmentTreeMax(){}
int query(int ql, int qr, int l = 0, int r = -2, int i = 1){
if(r == -2) r = len;
if(ql <= l && r <= qr) return S[i];
if(r <= ql || qr <= l) return 0;
int mid = (l+r)/2;
return max(query(ql,qr,l,mid,i*2), query(ql,qr,mid,r,i*2+1));
}
void upd(int i, int v){
i += len;
S[i] = v;
for(i /= 2; i > 0; i /= 2){
S[i] = max(S[i*2], S[i*2+1]);
}
}
};
int n;
vector<int> X;
vector<int> Y;
SegmentTree seg;
SegmentTreeMax segY;
int res = 0;
int solve(){
set<int> candidates;
for(int i = 1; i <= STEPS; i++){
// last pos with >= k 1s
int l = 0; int r = n-1;
int b = -1;
while(l <= r){
int mid = (l+r)/2;
int cnt = seg.query(mid, n).large;
if(cnt >= i){
b = max(b, mid);
l = mid+1;
}else{
r = mid-1;
}
}
candidates.insert(b);
}
candidates.erase(-1);
vector<int> cand(candidates.begin(),candidates.end());
cand.push_back(n);
int cur = seg.query(0,cand[0]).prod;
for(int I = 0; I < cand.size()-1; I++){
int i = cand[I];
int coefI = segY.query(i, cand[I+1]+1);
cur *= X[i];
cur %= mod;
int c = 1;
bool valid = false;
for(int J = I+1; J < cand.size()-1; J++){
int j = cand[J];
c *= X[j];
int coefJ = segY.query(j, cand[J+1]+1);
if(c > coefI || c *coefJ > coefI){
valid = true;
break;
}
}
if(!valid){
res = (cur * coefI)% mod;
return res;
}
}
res = (cur*Y[n-1])%mod;
return res;
}
int32_t init(int32_t N, int32_t mult[], int32_t cost[]) {
n = N;
X.resize(n);
Y.resize(n);
seg = SegmentTree(n);
segY = SegmentTreeMax(n);
for(int i = 0; i < n; i++){
X[i] = mult[i];
Y[i] = cost[i];
}
for(int i = 0;i < n; i++){
seg.upd(i, X[i]);
segY.upd(i, Y[i]);
}
return solve();
}
int32_t updateX(int32_t pos, int32_t val) {
X[pos] = val;
seg.upd(pos,val);
return solve();
}
int32_t updateY(int32_t pos, int32_t val) {
Y[pos] = val;
segY.upd(pos,val);
return solve();
}
