#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define sz(v) (int)(v.size())
const int MAXN = 5e5+5,MOD = 1e9+7;
ll x[MAXN],y[MAXN],bit[MAXN];
int n;
int binpow(int n,int k){
int res = 1;
while(k){
if(k&1)res = res * 1LL *n%MOD;
n = n*1LL*n%MOD;
k/=2;
}
return res;
}
void upd(int i,int val){
int j = i;
int c = binpow(x[i],MOD-2) * 1LL * val%MOD;
for(;i<=n;i+=i&(-i))bit[i] = bit[i] * 1LL *c %MOD;
x[j] = val;
}
int query(int i){
int res = 1;
for(;i>0;i-=i&(-i))res = res * 1LL * bit[i]%MOD;
return res;
}
int t[4*MAXN];
set<int,greater<int>>pip;
void upd(int v,int l,int r,int pos,int x){
if(l==r){
t[v] = x;
return;
}
int tm = (l+r)/2;
if(pos<=tm)upd(2*v,l,tm,pos,x);
else upd(2*v+1,tm+1,r,pos,x);
t[v] = max(t[2*v],t[2*v+1]);
}
int query(int v,int l,int r,int tl,int tr){
if(l>r)return 0;
if(l==tl && r==tr)return t[v];
int tm = (tl+tr)/2;
int a = query(2*v,l,min(r,tm),tl,tm);
int b = query(2*v+1,max(tm+1,l),r,tm+1,tr);
return max(a,b);
}
void build(int v,int l,int r){
if(l==r)t[v] = y[l];
else{
int tm = (l+r)/2;
build(2*v,l,tm);
build(2*v+1,tm+1,r);
t[v] = max(t[2*v],t[2*v+1]);
}
}
ll smort(){
vector<int>v;
for(int x:pip){
if(sz(v)>30)break;
v.push_back(x);
}
if(v.empty())return t[1];
if(sz(v)<=30 && v.back() != 1)v.push_back(1);
reverse(v.begin(),v.end());
v.push_back(n+1);
int m = sz(v);
vector<ll>Y(m,0);
for(int i=0;i<m-1;i++)Y[i] = query(1,v[i],v[i+1]-1,1,n);
int last = 0;
ll cur = 1;
for(int i=1;i+1<m;i++){
cur*=x[v[i]];
if(cur > Y[last]){
cur = 1;
last = i;
continue;
}
if(cur * Y[i] > Y[last]){
cur = 1;
last = i;
}
}
ll ans = query(v[last]);
ans = ans*Y[last]%MOD;
return ans;
}
int init(int N, int X[], int Y[]) {
n = N;
for(int i=1;i<=n;i++){
x[i] = X[i-1];
y[i] = Y[i-1];
}
for(int i=1;i<=n;i++)bit[i] = 1;
for(int i=1;i<=n;i++){
int tmp = x[i];
x[i] = 1;
upd(i,tmp);
if(x[i]>1)pip.insert(i);
}
build(1,1,n);
return smort();
}
int updateX(int pos, int val) {
pos++;
upd(pos,val);
if(val > 1)pip.insert(pos);
else if(pip.count(pos))pip.erase(pos);
return smort();
}
int updateY(int pos, int val) {
pos++;
y[pos] = val;
upd(1,1,n,pos,val);
return smort();
}
