#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<cstring>
#include<vector>
#include "horses.h"
using namespace std;
#define for1(i,n) for(int i=1;i<=(int)n;i++)
#define for0(i,n) for(int i=0;i<=(int)n;i++)
#define forn(i,n) for(int i=n;i>=1;i--)
#define fo(i,x,y) for(int i=x;i<=(int)y;i++)
#define fr(i,x,y) for(int i=x;i>=(int)y;i--)
#define pb push_back
#define mp make_pair
#define LL long long
const LL Mod=1000*1000*1000+7;
int n;
LL X[10002];
LL Y[10002];
struct vert
{
double gum;
double ans;
int pos;
}t[4*100002];
void combine(int v)
{
if(t[2*v].ans>=(t[2*v].gum+t[2*v+1].ans))
{
t[v].ans=t[2*v].ans;
t[v].pos=t[2*v].pos;
}
else
{
t[v].ans=(t[2*v].gum+t[2*v+1].ans);
t[v].pos=t[2*v+1].pos;
}
t[v].gum=(t[2*v].gum+t[2*v+1].gum);
}
void build(int left,int right,int v)
{
if(left==right)
{
t[v].gum=(double)log(X[left]);
t[v].ans=(double)log(X[left])+(double)log(Y[left]);
t[v].pos=left;
}
else
{
int m=(left+right)/2;
build(left,m,2*v);
build(m+1,right,2*v+1);
combine(v);
}
}
void update(int left,int right,int pos,int v)
{
if(left==right)
{
t[v].gum=(double)log(X[left]);
t[v].ans=(double)log(X[left])+(double)log(Y[left]);
t[v].pos=left;
}
else
{
int m=(left+right)/2;
if(pos<=m)
update(left,m,pos,2*v);
else
update(m+1,right,pos,2*v+1);
combine(v);
}
}
LL mult[4*100002];
void build2(int left,int right,int v)
{
if(left==right)
mult[v]=X[left];
else
{
int m=(left+right)/2;
build2(left,m,2*v);
build2(m+1,right,2*v+1);
mult[v]=((LL)mult[2*v]*(LL)mult[2*v+1])%Mod;
}
}
LL get2(int left,int right,int l,int r,int v)
{
if(l>r)
return 1;
if(left==l && right==r)
return mult[v];
int m=(left+right)/2;
LL A=get2(left,m,l,min(r,m),2*v);
LL B=get2(m+1,right,max(l,m+1),r,2*v+1);
return ((LL)A*(LL)B)%Mod;
}
void update2(int left,int right,int pos,int v)
{
if(left==right)
{
mult[v]=X[left];
}
else
{
int m=(left+right)/2;
if(pos<=m)
update2(left,m,pos,2*v);
else
update2(m+1,right,pos,2*v+1);
mult[v]=((LL)mult[2*v]*(LL)mult[2*v+1])%Mod;
}
}
int init(int n_0, int x_0[], int y_0[]) {
n=n_0;
for1(i,n)
X[i]=x_0[i-1];
for1(i,n)
Y[i]=y_0[i-1];
build(1,n,1);
build2(1,n,1);
return ((LL)get2(1,n,1,t[1].pos,1)*(LL)Y[t[1].pos])%Mod;
}
int updateX(int pos, int val) {
X[pos+1]=val;
update(1,n,pos+1,1);
update2(1,n,pos+1,1);
return ((LL)get2(1,n,1,t[1].pos,1)*(LL)Y[t[1].pos])%Mod;
}
int updateY(int pos, int val) {
Y[pos+1]=val;
update(1,n,pos+1,1);
return ((LL)get2(1,n,1,t[1].pos,1)*(LL)Y[t[1].pos])%Mod;
}
