#include "horses.h"
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define F first
#define S second
#define lc id*2+1
#define rc id*2+2
using namespace std;
const ll p=1e9+7;
ll pw(ll a,ll b){
ll ans=1;
while(b){
if(b&1)ans*=a,ans%=p;
b>>=1,a*=a,a%=p;
}
return ans;
}
ll x[500010],y[500010],n;
ld x2[500010],y2[500010],u[500010];
struct BIT{
ll ori[500010];
void init(){
for(int i=0;i<=n;i++)ori[i]=1;
return;
}
void modify(ll x,int pos){
while(pos<=n){
ori[pos]*=x;
ori[pos]%=p;
pos+=pos&(-pos);
}
return;
}
ll query(ll pos){
ll ans=1;
while(pos){
ans*=ori[pos];
ans%=p;
pos-=pos&(-pos);
}
return ans;
}
}bit;
struct node{
pair<ld,int> val;
ld tag;
node(){
}
};
struct SEG_TREE{
node ori[2000010];
void pull(int l,int r,int id){
if(l==r)return;
ori[id].val=max(ori[lc].val,ori[rc].val);
return;
}
void push(int l,int r,int id){
ori[id].val.F+=ori[id].tag;
if(l!=r){
int m=(l+r)>>1;
ori[lc].tag+=ori[id].tag;
ori[rc].tag+=ori[id].tag;
}
ori[id].tag=0;
return;
}
void build(int l,int r,int id){
ori[id].tag=0;
if(l==r){
ori[id].val={u[l],l};
return;
}
int m=(l+r)>>1;
build(l,m,lc);
build(m+1,r,rc);
pull(l,r,id);
return;
}
void modify(int l,int r,int ml,int mr,int id,ld x){
push(l,r,id);
if(l==ml&&r==mr){
ori[id].tag+=x;
push(l,r,id);
return;
}
int m=(l+r)>>1;
push(l,m,lc);
push(m+1,r,rc);
pull(l,r,id);
if(mr<=m){
modify(l,m,ml,mr,lc,x);
}else if(m<ml){
modify(m+1,r,ml,mr,rc,x);
}else{
modify(l,m,ml,m,lc,x);
modify(m+1,r,m+1,mr,rc,x);
}
push(l,m,lc);
push(m+1,r,rc);
pull(l,r,id);
return;
}
pair<ld,int> query(int l,int r,int ql,int qr,int id){
push(l,r,id);
if(l==ql&&r==qr){
return ori[id].val;
}
int m=(l+r)>>1;
if(qr<=m){
return query(l,m,ql,qr,lc);
}else if(m<ql){
return query(m+1,r,ql,qr,rc);
}else{
return max(query(l,m,ql,m,lc),query(m+1,r,m+1,qr,rc));
}
}
}seg;
ll q(){
pair<ld,int> ans=seg.query(1,n,1,n,0);
ll a=bit.query(ans.S);
a*=y[ans.S];
a%=p;
return a;
}
int init(int N, int X[], int Y[]) {
n=N;
for(int i=0;i<n;i++){
x[i+1]=X[i];
y[i+1]=Y[i];
}
bit.init();
for(int i=1;i<=n;i++){
x2[i]=log2l(x[i]);
y2[i]=log2l(y[i]);
bit.modify(x[i],i);
}
ld now=0;
for(int i=1;i<=n;i++){
now+=x2[i];
u[i]=now+y2[i];
}
seg.build(1,n,0);
return q();
}
int updateX(int pos, int val) {
pos+=1;
seg.modify(1,n,pos,n,0,log2l(val)-log2l(x[pos]));
bit.modify((pw(x[pos],p-2)*val)%p,pos);
x[pos]=val;
return q();
}
int updateY(int pos, int val) {
pos+=1;
seg.modify(1,n,pos,pos,0,log2l(val)-log2l(y[pos]));
y[pos]=val;
return q();
}
