#include "horses.h"
#include <vector>
#include <set>
using namespace std;
long long mod = 1e9 + 7;
struct segtree
{
int l;
int r;
long long mx = 0;
long long p_mod = 0;
long long p_actual = 0;
segtree* left;
segtree* right;
segtree()
{
;
}
segtree(int L, int R)
{
l = L;
r = R;
if(l == r) return;
int m = (l+r)/2;
left = new segtree(l, m);
right = new segtree(m+1, r);
}
void update(int I, int V)
{
if(I < l || r < I) return;
if(l == r) mx = p_mod = p_actual = V;
else
{
left->update(I, V);
right->update(I, V);
mx = max(left->mx, right->mx);
p_mod = (left->p_mod * right->p_mod) % mod;
p_actual = left->p_actual * right->p_actual;
}
}
long long rangemax(int L, int R)
{
if(R < l || r < L) return 0;
if(R <= l && r <= L) return mx;
return max(left->rangemax(L, R), right->rangemax(L, R));
}
long long rangeprod_actual(int L, int R)
{
if(R < l || r < L) return 1;
if(R <= l && r <= L) return p_actual;
return left->rangeprod_actual(L, R) * right->rangeprod_actual(L, R);
}
long long rangeprod_mod(int L, int R)
{
if(R < l || r < L) return 1;
if(R <= l && r <= L) return p_mod;
return (left->rangeprod_mod(L, R) * right->rangeprod_mod(L, R)) % mod;
}
};
struct growth
{
int i;
long long x;
};
bool operator < (growth A, growth B)
{
return A.i > B.i;
}
segtree X;
segtree Y;
set<growth> Xset;
int N;
int compute()
{
if(Xset.size() == 0) return Y.rangemax(0, N-1);
int maxprod_pos;
long long maxprod = 1;
for(growth g: Xset)
{
maxprod *= g.x;
maxprod_pos = g.i;
if(maxprod > 1e9) break;
}
int res_pos;
long long temp_res = 1;
for(growth g: Xset)
{
if(g.i < maxprod_pos) break;
if(X.rangeprod_actual(maxprod_pos, g.i) * Y.rangemax(g.i, N-1) >= temp_res)
{
temp_res = X.rangeprod_actual(maxprod_pos, g.i) * Y.rangemax(g.i, N-1);
res_pos = g.i;
}
}
return (X.rangeprod_mod(0, res_pos) * Y.rangemax(res_pos, N-1)) % mod;
}
int init(int n, int x[], int y[])
{
N = n;
X = segtree(0, n-1);
for(int i = 0; i < n; i++)
{
X.update(i, x[i]);
if(x[i] != 1) Xset.insert(growth{i, x[i]});
}
Y = segtree(0, n-1);
for(int i = 0; i < n; i++) Y.update(i, y[i]);
return compute();
}
int updateX(int pos, int val)
{
int curr_val = X.rangemax(pos, pos);
if(curr_val != 1) Xset.erase(growth{pos, curr_val});
X.update(pos, val);
if(val != 1) Xset.insert(growth{pos, val});
return compute();
}
int updateY(int pos, int val)
{
Y.update(pos, val);
return compute();
}
