#include "horses.h"
#define mp make_pair
#define f first
#define s second
#include <bits/stdc++.h>
using namespace std;
struct SegTree
{
int n;
vector<pair<int, double>> data;
vector<double> lazy;
SegTree(int n) : n(n), data(n<<2), lazy(n<<2) {}
pair<int, double> merge(pair<int, double> a, pair<int, double> b)
{
if (b.s > a.s)
return b;
else
return a;
}
void push(int l, int r, int index)
{
data[index].s += lazy[index];
if (r - l > 1)
{
lazy[index<<1] += lazy[index];
lazy[(index<<1)|1] += lazy[index];
}
lazy[index] = 0;
}
void update_range(int l, int r, int index, int ss, int ee, double val)
{
push(l, r, index);
if (ss >= r || l >= ee)
return;
if (ee >= r && l >= ss)
{
lazy[index] += val;
push(l, r, index);
return;
}
int m = l+r>>1;
update_range(l, m, index<<1, ss, ee, val);
update_range(m, r, (index<<1)|1, ss, ee, val);
data[index] = merge(data[index<<1], data[(index<<1)|1]);
}
void set(int l, int r, int index, int i, double val)
{
push(l, r, index);
if (i >= r || l > i)
return;
if (r - l == 1)
{
data[index].f = i;
data[index].s += val;
return;
}
int m = l+r>>1;
set(l, m, index<<1, i, val);
set(m, r, (index<<1)|1, i, val);
data[index] = merge(data[index<<1], data[(index<<1)|1]);
}
pair<int, double> get(int l, int r, int index, int ss, int ee)
{
push(l, r, index);
if (ss >= r || l >= ee)
return mp(-1, -1);
if (ee >= r && l >= ss)
return data[index];
int m = l+r>>1;
pair<int, double> lres = get(l, m, index<<1, ss, ee);
pair<int, double> rres = get(m, r, (index<<1)|1, ss, ee);
return merge(lres, rres);
}
void set(int i, double val) { set(0, n, 1, i, val); }
pair<int, double> get(int ss, int ee) { return get(0, n, 1, ss, ee); }
void update_range(int ss, int ee, double val) { update_range(0, n, 1, ss, ee, val); }
};
constexpr static int MXSIZE = 5e5;
constexpr static int MOD = 1e9 + 7;
double xl[MXSIZE];
double yl[MXSIZE];
int x[MXSIZE], y[MXSIZE];
int mul(int64_t a, int64_t b)
{
return (a * b) % MOD;
}
int st[MXSIZE<<1];
SegTree stm(0);
int n;
void update(int i, int val) { for (st[i+=n]=val;i>1;i>>=1) st[i>>1] = mul(st[i], st[i^1]); }
int get(int l, int r)
{
int res = 1;
for (l+=n,r+=n;l<r;l>>=1,r>>=1)
{
if (l&1) res = mul(res, st[l++]);
if (r&1) res = mul(res, st[--r]);
}
return res;
}
int get_best()
{
int i = stm.get(0, n).f;
return mul(get(0, i+1), y[i]);
}
int init(int N, int X[], int Y[])
{
n = N;
stm = SegTree(n);
for (int i = 0; i < n; i++)
{
x[i] = X[i];
y[i] = Y[i];
xl[i] = log2(x[i]);
yl[i] = log2(y[i]);
update(i, x[i]);
}
for (int i = 0; i < n; i++)
stm.set(i, yl[i]);
for (int i = 0; i < n; i++)
stm.update_range(i, n, xl[i]);
return get_best();
}
int updateY(int pos, int val)
{
y[pos] = val;
double _new = log2(val);
double change = _new - yl[pos];
yl[pos] = _new;
stm.set(pos, change);
return get_best();
}
int updateX(int pos, int val)
{
x[pos] = val;
update(pos, val);
double _new = log2(val);
double change = _new - xl[pos];
xl[pos] = _new;
stm.update_range(pos, n, change);
return get_best();
}
