#include "horses.h"
#include <bits/stdc++.h>
#define fo(a,b,c) for (int a=b;a<=c;a++)
#define F first
#define S second
using namespace std;
const int MAXN = 5e5+5,mod = 1e9+7;
typedef long long ll;
typedef pair<ll,ll> i2;
int n,x[MAXN],y[MAXN];
ll stX[4*MAXN],r;
i2 stY[4*MAXN];
set<int> Set;
ll ry;
i2 unu;
void iniX(int no,int in,int fin)
{
if (in == fin) {
stX[no] = x[in];
return;
}
int mid=(in+fin)/2;
iniX(no*2+1,in,mid);
iniX(no*2+2,mid+1,fin);
stX[no] = stX[no*2+1]*stX[no*2+2];
stX[no]%= mod;
return;
}
void iniY(int no,int in,int fin)
{
if (in == fin ) {
stY[no].F = y[in];
stY[no].S = in;
return;
}
int mid=(in+fin)/2;
iniY(no*2+1,in,mid);
iniY(no*2+2,mid+1,fin);
stY[no] = max(stY[no*2+1],stY[no*2+2]);
return;
}
void getX(int no,int in,int fin,int u,int v)
{
if (fin < u || in > v) return;
if (u<=in && fin <= v){
r *= stX[no];
r %= mod;
return;
}
int mid=(in+fin)/2;
getX(no*2+1,in,mid,u,v);
getX(no*2+2,mid+1,fin,u,v);
return;
}
void getY(int no,int in,int fin,int u,int v)
{
if (fin < u || in > v) return;
if (u<=in && fin <= v){
unu = max(unu,stY[no]);
return;
}
int mid=(in+fin)/2;
getY(no*2+1,in,mid,u,v);
getY(no*2+2,mid+1,fin,u,v);
return;
}
void updX(int no,int in,int fin,int u,int v)
{
if (fin < u || in > u) return;
if (u<=in && fin <= u){
stX[no] = v;
return;
}
int mid=(in+fin)/2;
updX(no*2+1,in,mid,u,v);
updX(no*2+2,mid+1,fin,u,v);
stX[no] = stX[no*2+1]*stX[no*2+2];
stX[no]%= mod;
return;
}
void updY(int no,int in,int fin,int u,int v)
{
if (fin < u || in > u) return;
if (u<=in && fin <= u){
stY[no].F = v;
return;
}
int mid=(in+fin)/2;
updY(no*2+1,in,mid,u,v);
updY(no*2+2,mid+1,fin,u,v);
stY[no] = max(stY[no*2+1],stY[no*2+2]);
return;
}
int sol()
{
ll k = 0; /// respuesta optima, empezando en pos = -1
ll res = -1; // indice res optima
ll q=1; // caballos
set<int>::iterator it = Set.end();
it--;
vector<int> posres;
int tp = 0;
while (true) {
if (tp > 35) {
break;
} else {
posres.push_back(*it);
tp++;
//cout << *it << " ";
if (it == Set.begin()) { break ;}
it--;
}
}
reverse(posres.begin(),posres.end());
posres.push_back(n);
if (posres.size()==1) {
unu.F=0;
unu.S = -1;
getY(0,0,n-1,0,n-1);
return unu.F;
} else {
// for (int u : posres) cout << u <<" " ;
for (int j=0;j<(int)posres.size()-1;j++) {
int i = posres[j];
ll ok = x[i];
ll owo = posres[j+1]-1;
unu.F = 0;
unu.S = -1;
getY(0,0,n-1,i,owo);
//cout << unu << " " ;
q *= ok;
if (k<=q) {
res = unu.S;
k = unu.F;
q = 1;
} else {
q *= unu.F;
if (k<=q) {
res = unu.S;
k = unu.F;
q = 1;
} else {
q /= unu.F;
}
}
}
r=1;
getX(0,0,n-1,0,res);
r %= mod;
r *= y[res];
r %= mod;
return r;
}
}
int init(int N, int X[], int Y[]) {
n = N;
fo(i,0,n-1) x[i] = X[i];
fo(i,0,n-1) y[i] = Y[i];
fo(i,0,n-1) if (x[i] != 1) Set.insert(i);
iniX(0,0,n-1);
iniY(0,0,n-1);
return sol();
}
int updateX(int pos, int val) {
if (x[pos] == 1 && val > 1) Set.insert(pos);
else {
if (x[pos] > 1 && val == 1) {
Set.erase(pos);
}
}
x[pos] = val;
updX(0,0,n-1,pos,val);
return sol();
}
int updateY(int pos, int val) {
y[pos] = val;
updY(0,0,n-1,pos,val);
return sol();
}
