//ideia Leonardo
#include <bits/stdc++.h>
#include "horses.h"
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const int MAXN = 500001;
const int MOD = 1e9+7;
struct seg{
ll id, v;
};
seg tree[4*MAXN];
ll mult[4*MAXN];
int *x, *y;
int n;
set<int> s; // todos os indices de x>=2
seg merge(seg a, seg b){
if(a.v<b.v)
return b;
return a;
}
void build(int id, int l, int r){
if(l==r){
tree[id] = {l, y[l]};
mult[id] = x[l];
return;
}
int e = id*2+1;
int d = id*2+2;
int m = (l+r)>>1;
build(e,l,m);
build(d,m+1,r);
tree[id] = merge(tree[e],tree[d]);
mult[id] = (mult[e]*mult[d])%MOD;
}
void update(int id, int l, int r, int q){
if(r< q || l > q){
return;
}
if(l==q && r == q){
tree[id] = {l,y[l]};
return;
}
int e = id*2+1;
int d = id*2+2;
int m = (l+r)>>1;
update(e,l,m,q);
update(d,m+1,r,q);
tree[id] = merge(tree[e],tree[d]);
}
seg query(int id, int l, int r, int ql, int qr){
if(ql > r || qr < l || qr < ql)
return {0,-1};
if(ql <= l && r <= qr)
return tree[id];
int e = id*2+1;
int d = id*2+2;
int m = (l+r)>>1;
return merge(query(e,l,m,ql,qr),query(d,m+1,r,ql,qr));
}
void updatemult(int id, int l, int r, int q){
if(q < l || q > r)
return;
if(l==q && r ==q){
mult[id] = x[l];
return;
}
int e = id*2+1;
int d = id*2+2;
int m = (l+r)>>1;
updatemult(e,l,m,q);
updatemult(d,m+1,r,q);
mult[id] = (mult[e]*mult[d])%MOD;
}
ll querymult(int id, int l, int r, int ql, int qr){
if(ql > r || qr < l || qr < ql)
return 1;
if(ql <= l && r <= qr)
return mult[id];
int e = id*2+1;
int d = id*2+2;
int m = (l+r)>>1;
return (querymult(e,l,m,ql,qr)*querymult(d,m+1,r,ql,qr))%MOD;
}
ll calc(){
auto it = s.rbegin();
//iterador reverso: começa na ultima posição e termina 1 a menos da primeira posição
seg resp = {0,0};
int r = n-1;
while(true){
if(it == s.rend()){
resp = merge(resp, query(0,0,n-1,0,r));
// compara a resposta atual com o bloco de 1 mais à esquerda
break;
}
resp = merge(resp,query(0,0,n-1,*it,r));
// compara a resposta atual com o próximo indice de x >= 2 e com o bloco de x = 1 à direita
resp.v*= x[*it];
r = *it-1;
if(resp.v > (ll)1e9)
break;
it++;
}
return (querymult(0,0,n-1,0,resp.id) * y[resp.id]) % MOD;
}
int init(int N ,int X[], int Y[]){
x = X;
y = Y;
// o X[] e Y[] continuam sendo válidos mesmo depois da chamada da funcão então eu vou usar *x e *y pra acessar o array
n = N;
build(0,0,n-1);
for(int i = 0; i < n; i++)
if(x[i] >= 2)
s.insert(i);
return calc();
}
int updateX(int pos, int val){
s.erase(pos);
x[pos] = val;
if(x[pos]>=2)
s.insert(pos);
updatemult(0,0,n-1,pos);
return calc();
}
int updateY(int pos, int val){
y[pos] = val;
update(0,0,n-1,pos);
return calc();
}
/*int main(){
int N, Q;
cin >> N >> Q;
int X[N], Y[N];
for(int i = 0; i < N; i++)
cin >> X[i];
for(int i = 0; i < N; i++)
cin >> Y[i];
cout << init(N,X,Y) << '\n';
for(int i = 0; i < Q; i++){
int t, a, b;
cin >> t >> a >> b;
if(t){
cout << updateY(a,b) << '\n';
} else{
cout << updateX(a,b) << '\n';
}
}
}*/
