#include <bits/stdc++.h>
#include "horses.h"
#define lli long long int
using namespace std;
const int N = 5e5 + 30;
const lli mod = 1e9 + 7;
lli bp(lli a, lli b = mod - 2)
{
lli ret = 1;
while(b)
{
if(b & 1) ret *= a, ret %= mod;
a *= a;
a %= mod;
b >>= 1;
}
return ret;
}
int n;
lli x[N], y[N], sum = 1;
lli t1[4 * N];
int t[4 * N];
void bld1(int l = 0, int r = n - 1, int nd = 1)
{
if(l == r)
{
t1[nd] = y[l];
return;
}
int mid = (l + r) / 2;
bld1(l, mid, nd * 2);
bld1(mid + 1, r, nd * 2 + 1);
t1[nd] = max(t1[nd * 2], t1[nd * 2 + 1]);
}
void upd1(int q, int l = 0, int r = n - 1, int nd = 1)
{
if(q > r || q < l) return;
if(l == r)
{
t1[nd] = y[q];
return;
}
int mid = (l + r) / 2;
upd1(q, l, mid, nd * 2);
upd1(q, mid + 1, r, nd * 2 + 1);
t1[nd] = max(t1[nd * 2], t1[nd * 2 + 1]);
}
lli qry1(int l, int r, int nl = 0, int nr = n - 1, int nd = 1)
{
if(l > nr || r < nl) return 0;
if(l == nl && r == nr) return t1[nd];
int mid = (nl + nr) / 2;
return max(qry1(l, min(mid, r), nl, mid, nd * 2), qry1(max(l, mid + 1), r, mid + 1, nr, nd * 2 + 1));
}
void bld(int l = 0, int r = n - 1, int nd = 1)
{
if(l == r)
{
t[nd] = l;
if(x[l] == 1) t[nd] = 0;
return;
}
int mid = (l + r) / 2;
bld(l, mid, nd * 2);
bld(mid + 1, r, nd * 2 + 1);
t[nd] = max(t[nd * 2], t[nd * 2 + 1]);
}
void upd(int q, int l = 0, int r = n - 1, int nd = 1)
{
if(q > r || q < l) return;
if(l == r)
{
t[nd] = l;
if(x[l] == 1) t[nd] = 0;
return;
}
int mid = (l + r) / 2;
upd(q, l, mid, nd * 2);
upd(q, mid + 1, r, nd * 2 + 1);
t[nd] = max(t[nd * 2], t[nd * 2 + 1]);
}
lli qry(int l, int r, int nl = 0, int nr = n - 1, int nd = 1)
{
if(l > nr || r < nl) return 0;
if(l == nl && r == nr) return t[nd];
int mid = (nl + nr) / 2;
return max(qry(l, min(mid, r), nl, mid, nd * 2), qry(max(l, mid + 1), r, mid + 1, nr, nd * 2 + 1));
}
lli slv()
{
//cout << "SM" << endl;
lli ss = sum, mx = 0, ret = 0;
int i1 = n - 1;
while(i1 >= 0 && mx < mod)
{
int ii = qry(0, i1);
mx = max(mx, qry1(ii, i1));
i1 = ii;
mx *= x[i1];
ss *= bp(x[ii]), ss %= mod;
i1--;
}
return ((mx % mod) * ss) % mod;
}
int init(int N, int X[], int Y[])
{
n = N;
for (int i = 0; i < n; i++) x[i] = X[i], y[i] = Y[i], sum *= x[i], sum %= mod;
bld();
bld1();
return slv();
}
int updateX(int pos, int val) {
sum *= bp(x[pos]), sum %= mod;
sum *= val, sum %= mod;
x[pos] = val;
upd(pos);
return slv();
}
int updateY(int pos, int val) {
y[pos] = val;
upd1(pos);
return slv();
}
