#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define per(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
const ll INF = 1'000'000'007;
struct Node {
ll lo,hi,id;
long double log_sum=0,val,madd=0;
Node *l,*r;
Node(const vll&x, const vll&y, long double add, ll L,ll R) : lo(L), hi(R) {
if(hi-lo==1) {
log_sum=logf64(x[lo])+add;
val=log_sum+logf64(y[lo]);
id=lo;
} else {
ll mid=(lo+hi)/2;
l=new Node(x,y,add,lo,mid);
r=new Node(x,y,l->log_sum,mid,hi);
log_sum=r->log_sum;
tie(val,id)=max(pair<long double,ll>(l->val,l->id),pair<long double,ll>(r->val,r->id));
}
//cout<<"lo = "<<lo<<" hi = "<<hi<<" log_sum = "<<log_sum<<" add = "<<add<<" val = "<<val<<endl;
}
void updateX(ll pos, long double v) { // v is new logx[pos] - prev logx[pos]
if(hi<=pos) return;
if(pos<=lo) {
madd+=v;
log_sum+=v;
val+=v;
return;
}
push();
l->updateX(pos,v);
r->updateX(pos,v);
tie(val,id)=max(pair<long double,ll>(l->val,l->id),pair<long double,ll>(r->val,r->id));
}
void updateY(ll pos, ll v) { // v is new y[pos]
if(pos<lo||hi<=pos) return;
if(hi-lo==1) {
val=log_sum+logf64(v);
return;
}
push();
l->updateY(pos,v);
r->updateY(pos,v);
tie(val,id)=max(pair<long double,ll>(l->val,l->id),pair<long double,ll>(r->val,r->id));
}
void push() {
if(madd!=0) {
l->updateX(0,madd);
r->updateX(0,madd);
madd=0;
}
}
};
struct Prod {
ll lo,hi,prod;
Prod *l,*r;
Prod(const vll&x,ll L,ll R) : lo(L), hi(R) {
if(hi-lo==1) {
prod=x[lo];
} else {
ll mid=(lo+hi)/2;
l=new Prod(x,lo,mid);
r=new Prod(x,mid,hi);
prod=l->prod*r->prod%INF;
}
}
ll query(ll R) {
if(R<=lo) return 1;
if(hi<=R) return prod;
return l->query(R)*r->query(R)%INF;
}
void updateX(ll pos,ll v) { // v is new x[pos]
if(pos<lo||hi<=pos) return;
if(hi-lo==1) {
prod=v;
return;
}
l->updateX(pos,v);
r->updateX(pos,v);
prod=l->prod*r->prod%INF;
}
};
vll x,y;
Node *segtree;
Prod *prodseg;
int init(int N, int X[], int Y[]) {
rep(i,0,N) {
assert(X[i]&&Y[i]);
x.pb(X[i]);
y.pb(Y[i]);
}
segtree=new Node(x,y,0,0,N);
prodseg=new Prod(x,0,N);
ll id=segtree->id;
return prodseg->query(id+1)*y[id]%INF;
}
int updateX(int pos, int val) {
assert(val);
double diff=logf64(val)-logf64(x[pos]);
x[pos]=val;
segtree->updateX(pos,diff);
prodseg->updateX(pos,val);
ll id=segtree->id;
return prodseg->query(id+1)*y[id]%INF;
}
int updateY(int pos, int val) {
assert(val);
y[pos]=val;
segtree->updateY(pos,val);
ll id=segtree->id;
return prodseg->query(id+1)*y[id]%INF;
}
