/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
typedef long long ll;
const int N_MAX = 500000;
const int BITS = 19;
const int MOD = 1e9+7;
int pwr (int a, int b)
{
if(b == 0)
return 1;
if(b & 1)
return 1LL * a * pwr(a, (b ^ 1)) % MOD;
int aux = pwr(a, (b >> 1));
return 1LL * aux * aux % MOD;
}
int n;
int x[N_MAX + 2];
int y[N_MAX + 2];
int SGT[N_MAX * 4 + 2];
void build (int node, int l, int r)
{
if(l == r)
{
SGT[node] = y[l];
return;
}
int mid = (l + r) / 2;
int lSon = node * 2, rSon = node * 2 + 1;
build(lSon, l, mid);
build(rSon, mid + 1, r);
SGT[node] = max(SGT[lSon], SGT[rSon]);
}
void build ()
{
build(1, 1, n);
}
void updateSGT (int node, int l, int r, int upos, int uval)
{
if(l == r)
{
SGT[node] = uval;
return;
}
int mid = (l + r) / 2;
int lSon = node * 2, rSon = node * 2 + 1;
if(upos <= mid)
updateSGT(lSon, l, mid, upos, uval);
else
updateSGT(rSon, mid + 1, r, upos, uval);
SGT[node] = max(SGT[lSon], SGT[rSon]);
}
void updateSGT (int upos, int uval)
{
updateSGT(1, 1, n, upos, uval);
}
int querySGT (int node, int l, int r, int ql, int qr)
{
if(ql <= l && r <= qr)
return SGT[node];
int mid = (l + r) / 2;
int lSon = node * 2, rSon = node * 2 + 1;
int answer = INT_MIN;
if(ql <= mid)
answer = max(answer, querySGT(lSon, l, mid, ql, qr));
if(mid + 1 <= qr)
answer = max(answer, querySGT(rSon, mid + 1, r, ql, qr));
return answer;
}
int querySGT (int ql, int qr)
{
return querySGT(1, 1, n, ql, qr);
}
int BIT[N_MAX + 2];
void updateBIT (int upos, int uval)
{
for(int i = upos; i <= n; i += i & -i)
BIT[i] = 1LL * BIT[i] * uval % MOD;
}
int queryBIT (int upos)
{
int answer = 1;
for(int i = upos; i >= 1; i -= i & -i)
answer = 1LL * answer * BIT[i] % MOD;
return answer;
}
int query ()
{
vector <pair <int, int>> segments;
int prod = 1;
int R = n;
while(1 <= R)
{
int Rpref = queryBIT(R);
int L = 0;
int Lpref = 1;
for(int bit = BITS - 1; bit >= 0; bit--)
if(L + (1 << bit) < R && 1LL * Lpref * BIT[L + (1 << bit)] % MOD != Rpref)
{
L += (1 << bit);
Lpref = 1LL * Lpref * BIT[L] % MOD;
}
L++;
segments.push_back(make_pair(L, R));
if(1000000000 / prod < x[L])
break;
prod *= x[L];
R = L - 1;
}
reverse(segments.begin(), segments.end());
prod = 1;
ll answer = 0;
for(pair <int, int> seg : segments)
{
int L = seg.first;
int R = seg.second;
if(L != segments.front().first)
prod *= x[L];
int bestY = querySGT(L, R);
answer = max(answer, 1LL * prod * bestY);
}
answer = answer % MOD * queryBIT(segments.front().first) % MOD;
return answer;
}
int init (int _n, int _x[], int _y[])
{
n = _n;
for(int i = 1; i <= n; i++)
x[i] = _x[i - 1];
for(int i = 1; i <= n; i++)
y[i] = _y[i - 1];
for(int i = 1; i <= n; i++)
BIT[i] = 1;
for(int i = 1; i <= n; i++)
updateBIT(i, x[i]);
build();
return query();
}
int updateX (int upos, int uval)
{
upos++;
updateBIT(upos, pwr(x[upos], MOD - 2));
x[upos] = uval;
updateBIT(upos, x[upos]);
return query();
}
int updateY (int upos, int uval)
{
upos++;
y[upos] = uval;
updateSGT(upos, y[upos]);
return query();
}
