#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10 , mod = 1e9 + 7;
int n , x[N] , y[N] , mulx;
set <int> st;
int tav(int a , int b)
{
int res = 1;
while(b)
{
if(b & 1)
res = 1LL * res * a % mod;
b >>= 1;
a = 1LL * a * a % mod;
}
return res;
}
struct SEG{
int mx[N << 4];
void Build(int node = 1 , int nl = 0 , int nr = n)
{
if(nr - nl == 1)
{
mx[node] = y[nl];
return;
}
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
Build(lc , nl , mid); Build(rc , mid , nr);
mx[node] = max(mx[lc] , mx[rc]);
}
void Update(int id , int node = 1 , int nl = 0 , int nr = n)
{
if(nr - nl == 1)
{
mx[node] = y[nl];
return;
}
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
if(id < mid)
Update(id , lc , nl , mid);
else
Update(id , rc , mid , nr);
mx[node] = max(mx[lc] , mx[rc]);
}
int Get(int l , int r , int node = 1 , int nl = 0 , int nr = n)
{
if(r <= nl || nr <= l)
return 0;
if(l <= nl && nr <= r)
return mx[node];
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
return max(Get(l , r , lc , nl , mid) , Get(l , r , rc , mid , nr));
}
} seg;
int Solve()
{
long long tmpx = 1 , mx_x = 1 , mx_y = 1;
for(auto asd : st)
{
auto u = abs(asd);
int Y = seg.Get(u , n);
if(Y > 1LL * mx_x * mx_y)
{
mx_y = Y;
mx_x = x[u];
}
else
{
mx_x *= x[u];
}
tmpx *= x[u];
if(mx_x * mx_y > mod)
break;
}
int res = mx_x * mx_y % mod;
return 1LL * mulx * tav(tmpx , mod - 2) % mod * res % mod;
}
int init(int nn, int X[], int Y[]) {
mulx = 1;
n = nn;
for(int i = 0 ; i < n ; i++)
{
x[i] = X[i];
y[i] = Y[i];
mulx = 1LL * mulx * x[i] % mod;
}
seg.Build();
for(int i = 0 ; i < n ; i++) if(x[i] > 1)
st.insert(-i);
return Solve();
}
int updateX(int pos, int val) {
if(x[pos] > 1)
st.erase(-pos);
mulx = 1LL * mulx * tav(x[pos] , mod - 2) % mod;
x[pos] = val;
if(x[pos] > 1)
st.insert(-pos);
mulx = 1LL * mulx * x[pos] % mod;
return Solve();
}
int updateY(int pos, int val) {
y[pos] = val;
seg.Update(pos);
return Solve();
}
