#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
int n;
long long x[500000];
long long y[500000];
long long all=1;
const int mod=1e9+7;
const int sz=524288;
int seg[sz*2];
set<int> s;
typedef pair<long long,long long> P;
int sum(int l,int r,int node=1,int nodel=0,int noder=sz-1) {
if (r<nodel||l>noder) {
return 0;
}
if (l<=nodel&&noder<=r) {
return seg[node];
}
int mid=(nodel+noder)/2;
return max(sum(l,r,node*2,nodel,mid),sum(l,r,node*2+1,mid+1,noder));
}
void update(int i,int val) {
i+=sz;
seg[i]=val;
while (i>1) {
i/=2;
seg[i]=max(seg[i*2],seg[i*2+1]);
}
}
long long fastpow(long long a,long long b) {
if (b==0) {
return 1;
}
if (b%2==1) {
return (fastpow(a,b-1)*a)%mod;
}
long long half=fastpow(a,b/2);
return (half*half)%mod;
}
int init(int N, int X[], int Y[]) {
n=N;
for(int i=0;i<n;i++) {
x[i]=X[i];
y[i]=Y[i];
update(i,y[i]);
all*=x[i];
all%=mod;
if (x[i]!=1) {
s.insert(i);
}
}
int pr=-1;
P mx=P(0,1);
long long gop=1;
if (s.empty()) {
return sum(0,n-1);
}
auto iter=prev(s.end());
pr=n;
while (1) {
int now=*iter;
if (mx.first*gop<sum(now,pr-1)*mx.second) { // mx.first/mx.second > y[now]/gop
mx=P(sum(now,pr-1),gop);
}
gop*=x[now];
if (gop>mod||iter==s.begin()) {
break;
}
iter--;
pr=now;
}
long long val=mx.first*fastpow(mx.second,mod-2);
val%=mod;
return (all*val)%mod;
}
int updateX(int pos, int val) {
if (x[pos]!=1&&val==1) {
s.erase(pos);
}
else if (x[pos]==1&&val!=1) {
s.insert(pos);
}
x[pos]=val;
P mx=P(0,1);
long long gop=1;
if (s.empty()) {
return sum(0,n-1);
}
auto iter=prev(s.end());
int pr=n;
while (1) {
int now=*iter;
if (mx.first*gop<sum(now,pr-1)*mx.second) { // mx.first/mx.second > y[now]/gop
mx=P(sum(now,pr-1),gop);
}
gop*=x[now];
if (gop>mod||iter==s.begin()) {
break;
}
pr=now;
iter--;
}
long long vl=mx.first*fastpow(mx.second,mod-2);
vl%=mod;
return (all*vl)%mod;
}
int updateY(int pos, int val) {
update(pos,val);
P mx=P(0,1);
long long gop=1;
if (s.empty()) {
return sum(0,n-1);
}
auto iter=prev(s.end());
int pr=n;
while (1) {
int now=*iter;
if (mx.first*gop<sum(now,pr-1)*mx.second) { // mx.first/mx.second > y[now]/gop
mx=P(sum(now,pr-1),gop);
}
gop*=x[now];
if (gop>mod||iter==s.begin()) {
break;
}
pr=now;
iter--;
}
long long vl=mx.first*fastpow(mx.second,mod-2);
vl%=mod;
return (all*vl)%mod;
}
