#include "horses.h"
#include <iostream>
#include <string>
#include <set>
#include <vector>
using namespace std;
long long mod = 1e9 + 7;
long long ll(int a)
{
return (long long)(a);
}
struct LLL
{
vector<int> d = vector<int>(5, 0);
LLL()
{
;
}
LLL(long long X)
{
d[0] = X;
}
};
LLL operator * (LLL A, LLL B)
{
LLL res;
for(int i = 0; i < 4; i++)
{
for(int j = 0; i+j < 4; j++)
{
res.d[i+j] += A.d[i] * B.d[j];
res.d[i+j+1] += res.d[i+j] / 1000000000;
res.d[i+j] = res.d[i+j] % 1000000000;
}
}
return res;
}
bool operator < (LLL A, LLL B)
{
for(int i = 4; i >= 0; i++)
{
if(A.d[i] < B.d[i]) return 1;
if(A.d[i] > B.d[i]) return 0;
}
return 0;
}
struct segtree
{
int l;
int r;
long long p_mod = 1;
LLL p_actual = LLL(1);
long long mx = 1;
segtree* left = NULL;
segtree* right = NULL;
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);
}
long long rangeprod_mod(int L, int R)
{
if(L > R) return 1;
if(r < L || R < l) return 1;
if(L <= l && r <= R) return p_mod;
return (left->rangeprod_mod(L, R) * right->rangeprod_mod(L, R)) % mod;
}
LLL rangeprod_actual(int L, int R)
{
if(L > R) return LLL(1);
if(r < L || R < l) return LLL(1);
if(L <= l && r <= R)
{
// cout << L << ' ' << R << ' ' << l << ' ' << r << ' ' << "rpa" << ' ' << p_actual.d[1] << p_actual.d[0] << '\n';
return p_actual;
}
else
{
return left->rangeprod_actual(L, R) * right->rangeprod_actual(L, R);
}
}
long long rangemax(int L, int R)
{
if(r < L || R < l) return 0;
if(L <= l && r <= R) return mx;
return max(left->rangemax(L, R), right->rangemax(L, R));
}
void update(int I, long long V)
{
if(I < l || r < I) return;
if(l == r)
{
p_mod = mx = V;
p_actual = LLL(V);
// cout << "build " << l << ' ' << r << ' ' << p_actual.d[1] << ' ' << p_actual.d[0] << '\n';
}
else
{
left->update(I, V);
right->update(I, V);
p_mod = (left->p_mod * right->p_mod) % mod;
p_actual = left->p_actual * right->p_actual;
mx = max(left->mx, right->mx);
// cout << "build " << l << ' ' << r << ' ' << p_actual.d[1] << ' ' << p_actual.d[0] << '\n';
}
}
};
struct growth
{
int i;
long long x;
};
bool operator < (growth A, growth B)
{
return A.i > B.i;
}
int N;
segtree X;
segtree Y;
set<growth> Xset;
int compute()
{
LLL maxprod = LLL(1);
int maxprod_pos = -1;
for(growth g: Xset)
{
maxprod = maxprod * LLL(g.x);
maxprod_pos = g.i;
if(LLL(1e9) < maxprod) break;
} //maxprod_pos is the first position with a suffix product > 1e9
LLL res = 0;
int res_pos = 0;
// for(int i = 0; i < N; i++) cout << X.rangeprod_mod(i, i) << ' ';
// cout << '\n';
// for(int i = 0; i < N; i++) cout << X.rangeprod_actual(i, i) << ' ';
// cout << '\n';
// for(int i = 0; i < N; i++) cout << Y.rangemax(i, i) << ' ';
// cout << '\n';
// cout << maxprod_pos << '\n';
for(growth g: Xset)
{
// cout << g.i << ' ' << g.x << '\n';
if(g.i < maxprod_pos) break;
if(LLL(res) < X.rangeprod_actual(maxprod_pos, g.i) * LLL(Y.rangemax(g.i, N-1)))
{
// cout << "prod " << ' ' << maxprod_pos << ' ' << g.i << " " << X.rangeprod_actual(maxprod_pos, g.i).d[0] << ' ' << Y.rangemax(g.i, N-1) << '\n';
res = X.rangeprod_actual(maxprod_pos, g.i) * LLL(Y.rangemax(g.i, N-1));
res_pos = g.i;
}
// if(g.i > 0 && X.rangeprod_actual(maxprod_pos, g.i-1) * Y.rangemax(g.i-1, N-1) > res)
// {
// res = X.rangeprod_actual(maxprod_pos, g.i-1) * Y.rangemax(g.i-1, N-1);
// res_pos = g.i-1;
// }
}
// cout << res_pos << '\n';
return int( (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);
Y = segtree(0, N-1);
for(int i = 0; i < N; i++)
{
X.update(i, x[i]);
if(x[i] != 1) Xset.insert(growth{i, ll(x[i])});
Y.update(i, ll(y[i]));
}
return compute();
}
int updateX(int pos, int val)
{
X.update(pos, val);
Xset.erase(growth{pos, val});
if(val != 1) Xset.insert(growth{pos, val});
return compute();
}
int updateY(int pos, int val)
{
Y.update(pos, val);
return compute();
}
