#include <bits/stdc++.h>
#include "horses.h"
#define ll long long
#define lp(i,a,b) for(int i=a;i<b;i++)
const int MAXN=5e5+5 ;
const int MOD=1e9+7 ;
using namespace std ;
// -------------x-------------
int n, x[MAXN],y[MAXN] ;
struct node
{
double v , l ;
int best ;
ll real ;
} ;
node tree[MAXN*4] ;
// -------------x-------------
int m(int l, int r) {return (l+r)/2 ;}
void refresh(int pos, int l, int r)
{
double k = tree[pos].l ;
tree[pos].l = 0 ;
tree[pos].v += k ;
if(l==r) return ;
lp(i,0,2) tree[pos*2+i].l += k ;
}
void merge(int pos)
{
tree[pos] = (tree[pos*2].v > tree[pos*2+1].v) ? tree[pos*2] : tree[pos*2+1] ;
tree[pos].real = tree[pos*2].real * tree[pos*2+1].real % MOD ;
}
void build(int pos, int l, int r)
{
if(l==r)
{
tree[pos].v = log2(y[l]) ;
tree[pos].real = x[l] ;
tree[pos].best = l ;
tree[pos].l = 0 ;
return ;
}
build(pos*2,l,m(l,r)) ;
build(pos*2+1, m(l,r)+1,r) ;
merge(pos) ;
}
void pointUpd(int pos, int l, int r, int x, int val)
{
refresh(pos,l,r) ;
if(l>x || r<x) return ;
if(l==r)
{
tree[pos].real = val ;
return ;
}
pointUpd(pos*2,l,m(l,r),x,val) ;
pointUpd(pos*2+1,m(l,r)+1,r,x,val) ;
merge(pos) ;
}
void intervalUpd(int pos, int l, int r, int beg, int en, double val )
{
refresh(pos,l,r) ;
if(l>en || r<beg) return ;
if(l>=beg && r<=en)
{
tree[pos].l += val ;
refresh(pos,l,r) ;
return ;
}
intervalUpd(pos*2,l,m(l,r),beg,en,val) ;
intervalUpd(pos*2+1,m(l,r)+1,r,beg,en,val) ;
merge(pos) ;
}
ll query(int pos, int l, int r, int beg, int en)
{
if(l>en || r<beg) return 1 ;
if(l>=beg && r<=en) return tree[pos].real ;
ll rl = query(pos*2,l,m(l,r),beg,en) ;
ll rr=query(pos*2+1,m(l,r)+1,r,beg,en) ;
return rl*rr%MOD ;
}
int ans()
{
refresh(1,0,n-1) ;
int myBest = tree[1].best ;
return query(1,0,n-1,0,myBest)*y[myBest]%MOD ;
}
int init(int N, int X[] , int Y[])
{
n=N;
lp(i,0,n) x[i]=X[i],y[i]=Y[i] ;
build(1,0,n-1) ;
lp(i,0,n) intervalUpd(1,0,n-1,i,n-1,log2(x[i])) ;
return ans() ;
}
int updateY(int pos, int val)
{
intervalUpd(1,0,n-1,pos,pos,-log2(y[pos]) + log2(val)) ;
y[pos]=val ;
return ans() ;
}
int updateX(int pos, int val)
{
pointUpd(1,0,n-1,pos,val) ;
intervalUpd(1,0,n-1,pos,n-1,-log2(x[pos])+log2(val) ) ;
x[pos]=val ;
return ans() ;
}
