#include<bits/stdc++.h>
#define pb push_back
#include "horses.h"
using namespace std;
const int maxn = 5e5 + 10;
const long long mod = 1e9 + 7;
long long n, a[maxn], b[maxn];
long long t[maxn * 4], ti[maxn * 4], tg[maxn * 4];
void build(int i, int l, int r)
{
t[i] = b[l];
ti[i] = l;
tg[i] = a[l];
if(l == r)return;
int mid = (l + r)/2;
build(2*i, l, mid);
build(2*i+1, mid+1, r);
t[i] = max(t[2*i], t[2*i+1]);
if(t[2*i] > t[2*i+1])ti[i] = ti[2*i];
else ti[i] = ti[2*i+1];
tg[i] = tg[2*i] * tg[2*i+1];
tg[i] %= mod;
}
long long updpos, updval;
void update_prod(int i, int l, int r)
{
if(l == r)
{
tg[i] = updval;
a[l] = updval;
return;
}
int mid = (l + r)/2;
if(updpos <= mid)update_prod(2*i, l, mid);
else update_prod(2*i+1, mid+1, r);
tg[i] = 1LL * tg[2*i] * tg[2*i+1];
tg[i] %= mod;
}
void update_max(int i, int l, int r)
{
if(l == r)
{
b[l] = updval;
ti[i] = l;
t[i] = b[l];
return;
}
int mid = (l + r)/2;
if(updpos <= mid)update_max(2*i, l, mid);
else update_max(2*i+1, mid+1, r);
t[i] = max(t[2*i], t[2*i+1]);
if(t[2*i] > t[2*i+1])ti[i] = ti[2*i];
else ti[i] = ti[2*i+1];
}
int ql, qr;
long long query_prod(int i, int l, int r)
{
if(l > r)return 1;
if(ql > r || qr < l)return 1;
if(ql <= l && r <= qr)return tg[i];
int mid = (l + r)/2;
long long pos1 = query_prod(2*i, l, mid);
long long pos2 = query_prod(2*i+1, mid+1, r);
return (pos1 * pos2) % mod;
}
long long query_max(int i, int l, int r)
{
if(l > r)return 0;
if(ql > r || qr < l)return 0;
if(ql <= l && r <= qr)return ti[i];
int mid = (l + r)/2;
int pos1 = query_max(2*i, l, mid);
int pos2 = query_max(2*i+1, mid+1, r);
if(!pos1 || !pos2)return (pos1 + pos2);
if(b[pos1] > b[pos2])return pos1;
else return pos2;
}
set < int > s;
int cnt = 0;
long long solve()
{
cnt ++;
if(s.size() == 0)
{
ql = 1;
qr = n;
// cout << pos << " " << n << endl;
return b[query_max(1, 1, n)];
}
s.insert(1);
set < int >::iterator it = s.end();
long long best = 0, bestsell = 0, index = 1;
while(it != s.begin())
{
int pre = n;
if(it != s.end())pre = *it - 1;
it --;
long long pos = *it;
// if(cnt < 10)cout << pre << " " << pos << endl;
ql = pos;
qr = pre;
long long sell = b[query_max(1, 1, n)];
// if(cnt < 10)cout << "sell is " << sell << endl;
if(sell > best)
{
best = sell;
index = pos;
bestsell = sell;
}
best *= a[pos];
if(best > 1LL * 1e9)break;
}
s.erase(1);
// cout << bestprod << " " << bestsell << endl;
ql = 1;
qr = index;
return 1LL * (bestsell * query_prod(1, 1, n))%mod;
}
int init(int N, int X[], int Y[])
{
n = N;
for (int i = 0; i < n; ++ i)
a[i+1] = X[i];
for (int i = 0; i < n; ++ i)
b[i+1] = Y[i];
build(1, 1, n);
for (int i = 1; i <= n; ++ i)
if(a[i] > 1)s.insert(i);
long long ans = solve();
//cout << "ans s " << ans << endl;
return ans;
}
int updateX(int pos, int val)
{
pos ++;
if(a[pos] > 1)s.erase(pos);
updpos = pos;
updval = val;
update_prod(1, 1, n);
if(val > 1)s.insert(pos);
return solve();
}
int updateY(int pos, int val)
{
pos ++;
b[pos] = val;
updpos = pos;
updval = val;
update_max(1, 1, n);
return solve();
}
