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