#include <bits/stdc++.h>
#include "horses.h"
#define lp(i,a,b) for(int i=a;i<b;i++)
#define ll long long
const int maxn=5e3+10 ;
const int MOD=1e9+7 ;
using namespace std ;
struct seg
{
double tree[maxn*4] ;
double lazy[maxn*4] ;
ll realVal[maxn*4] ;
int m(int l, int r){return (l+r)/2 ;}
void build(int pos, int l, int r)
{
realVal[pos]=1 ;
if(l==r) return ;
build(pos*2, l, m(l,r) ) ;
build(pos*2+1, m(l,r)+1,r) ;
}
void updRealVal(int pos, double k)
{
ll kk = 1LL*pow(2,k) ;
realVal[pos] = (realVal[pos]*kk) % MOD ;
}
void merge(int pos)
{
tree[pos] = max(tree[pos*2], tree[pos*2+1]) ;
realVal[pos] = (tree[pos*2] > tree[pos*2+1]) ? realVal[pos*2] : realVal[pos*2+1] ;
}
void refresh(int pos, int l, int r)
{
double k=lazy[pos] ;
lazy[pos]=0 ;
tree[pos] += k ;
updRealVal(pos,k) ;
if(l==r) return ;
lazy[pos*2]+=k;
lazy[pos*2+1]+=k;
}
void pointUpd(int pos,int l,int r,int x, double val)
{
refresh(pos, l, r) ;
if(l>x || r<x) return ;
if(l==r)
{
tree[pos] += val ;
updRealVal(pos,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)
{
lazy[pos] += 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) ;
}
} ;
// -------- x --------
int n ;
int x[maxn] , y[maxn] ;
seg mySeg ;
int updateX(int pos, int val)
{
double newVal = 1.0*val/x[pos] ;
x[pos] = val ;
newVal = log2(newVal) ;
mySeg.intervalUpd(1,0,n-1,pos,n-1,newVal) ;
mySeg.refresh(1,0,n-1) ;
return mySeg.realVal[1] ;
}
int updateY(int pos, int val)
{
double newVal = 1.0*val/y[pos] ;
y[pos]=val ;
newVal = log2(newVal) ;
mySeg.pointUpd(1,0,n-1,pos,newVal) ;
mySeg.refresh(1,0,n-1) ;
return mySeg.realVal[1] ;
}
int init(int N, int X[], int Y[])
{
n=N ;
lp(i,0,n) x[i]=X[i] ;
lp(i,0,n) y[i] = Y[i] ;
mySeg.build(1,0,n-1) ;
double acProduct = log2(1) ;
lp(i,0,n)
{
acProduct += log2(x[i]) ;
mySeg.pointUpd(1,0,n-1,i,acProduct+log2(y[i])) ;
}
return mySeg.realVal[1] ;
}
