#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
const ll inf=1e18;
const int MAXN=5e5+10;
const ll MOD=1e9+7;
struct node{
ll id,lp,rp;
bool modl,modr;
};
int n;
ll x[MAXN],y[MAXN];
node seg[4*MAXN];
node merge(node a,node b){
node c;
ll pro=a.rp*b.lp;
bool md=0;
if(pro>MOD) md=1,pro%=MOD;
pro*=x[b.id];
if(pro>MOD) md=1,pro%=MOD;
if(a.modr || b.modl || md || pro*y[b.id]>y[a.id]){
c.id=b.id;
c.modl=a.modl|b.modl|a.modr;
c.lp=a.lp*b.lp;
if(c.lp>MOD) c.lp%=MOD,c.modl=1;
c.lp*=a.rp;
if(c.lp>MOD) c.lp%=MOD,c.modl=1;
c.lp*=x[a.id];
if(c.lp>MOD) c.lp%=MOD,c.modl=1;
c.modr=b.modr;
c.rp=b.rp;
}
else{
c.id=a.id;
c.modr=a.modr|b.modr|b.modl;
c.rp=a.rp*b.lp;
if(c.rp>MOD) c.rp%=MOD,c.modr=1;
c.rp*=b.rp;
if(c.rp>MOD) c.rp%=MOD,c.modr=1;
c.rp*=x[b.id];
if(c.rp>MOD) c.rp%=MOD,c.modr=1;
c.modl=a.modl;
c.lp=a.lp;
}
return c;
}
void build(int ind,int l,int r){
if(l==r){
seg[ind].id=l;
seg[ind].lp=1;
seg[ind].rp=1;
seg[ind].modl=seg[ind].modr=0;
return;
}
int m=(l+r)/2; build(2*ind,l,m); build(2*ind+1,m+1,r);
seg[ind]=merge(seg[2*ind],seg[2*ind+1]);
}
void updt(int ind,int l,int r,int a){
if(l==r) return;
int m=(l+r)/2;
if(a<=m) updt(2*ind,l,m,a);
else updt(2*ind+1,m+1,r,a);
seg[ind]=merge(seg[2*ind],seg[2*ind+1]);
}
int init(int N, int X[], int Y[]){
n=N;
fall(i,0,n-1) x[i]=X[i],y[i]=Y[i];
build(1,0,n-1);
ll ans=x[seg[1].id]*seg[1].lp % MOD * y[seg[1].id] % MOD;
return ans;
}
int updateX(int pos, int val){
x[pos]=val;
updt(1,0,n-1,pos);
ll ans=x[seg[1].id]*seg[1].lp % MOD * y[seg[1].id] % MOD;
return ans;
}
int updateY(int pos, int val) {
y[pos]=val;
updt(1,0,n-1,pos);
ll ans=x[seg[1].id]*seg[1].lp % MOD * y[seg[1].id] % MOD;
return ans;
}
