#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
template<class X, class Y>
inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
const int MAXN = 500005;
const int modl = 1e9+7;
ll seg[4 * MAXN];
int dp[12][MAXN], X[MAXN], Y[MAXN], nArr;
ll powermod(ll a, int exponent) {
ll res(1);
while(exponent > 0) {
if(exponent & 1)
res = res * a % modl;
a = a * a % modl;
exponent >>= 1;
}
return res;
}
int segx[4 * MAXN], segy[4 * MAXN];
void build(int seg[], int id, int l, int r, int x[]) {
if(l == r) {
seg[id] = x[l];
return;
}
int mid = (l + r) >> 1;
build(seg, id << 1, l, mid, x);
build(seg, id << 1 | 1, mid + 1, r, x);
seg[id] = max(seg[id << 1], seg[id << 1 | 1]);
}
void update(int seg[], int pos, int val) {
int id(1), l(1), r(nArr);
while(l != r) {
int mid = (l + r) >> 1;
if(pos <= mid) {
id = id << 1;
r = mid;
} else {
id = id << 1 | 1;
l = mid + 1;
}
}
seg[id] = val;
while(id > 1) {
id >>= 1;
seg[id] = max(seg[id << 1], seg[id << 1 | 1]);
}
}
int query(int seg[], int id, int l, int r, int u, int v) {
if(u <= l && r <= v)
return seg[id];
int mid = (l + r) >> 1, res(0);
if(mid >= u)
res = max(res, query(seg, id << 1, l, mid, u, v));
if(mid < v)
res = max(res, query(seg, id << 1 | 1, mid + 1, r, u, v));
return res;
}
int findFirst(int seg[], int id, int l, int r, int pos, int k) {
if(seg[id] < k || pos > r)
return nArr + 1;
if(pos <= l) {
while(l != r) {
int mid = (l + r) >> 1;
if(seg[id << 1] < k) {
id = id << 1 | 1;
l = mid + 1;
} else {
id = id << 1;
r = mid;
}
}
return l;
}
int mid = (l + r) >> 1;
return min(findFirst(seg, id << 1, l, mid, pos, k), findFirst(seg, id << 1 | 1, mid + 1, r, pos, k));
}
void modify(int pos, int val) {
int id(1), l(1), r(nArr);
while(l != r) {
int mid = (l + r) >> 1;
if(pos <= mid) {
id = id << 1;
r = mid;
} else {
id = id << 1 | 1;
l = mid + 1;
}
}
seg[id] = val;
while(id > 1) {
id >>= 1;
seg[id] = min(ll(1e9)+1, 1LL * seg[id << 1] * seg[id << 1 | 1]);
}
}
int get(int id, int l, int r, int u, int v) {
if(v < l || u > r)
return 1;
if(u <= l && r <= v)
return seg[id];
int mid = (l + r) >> 1;
return min(ll(1e9)+1, 1LL * get(id << 1, l, mid, u, v) * get(id << 1 | 1, mid + 1, r, u, v));
}
int calcDP(void) {
int MAX_HORSE(1);
for (int i = 1; i <= nArr; ++i)
MAX_HORSE *= X[i];
for (int i = 0; i <= nArr; ++i) {
for (int k = 0; k <= MAX_HORSE; ++k)
dp[i][k] = -1;
}
dp[0][1] = 0;
for (int i = 0; i < nArr; ++i) {
for (int k = 0; k <= MAX_HORSE; ++k) {
if(dp[i][k] < 0)
continue;
maximize(dp[i + 1][k * X[i + 1]], dp[i][k]);
}
for (int k = MAX_HORSE; k > 0; --k) {
if(dp[i + 1][k] < 0)
continue;
maximize(dp[i + 1][k - 1], dp[i + 1][k] + Y[i + 1]);
}
}
return dp[nArr][0];
}
struct Bignum {
static const int MAX_DIGIT = 1000;
static const int BASE = (int) 1e9;
int digits[MAX_DIGIT], numDigit;
Bignum(ll x = 0) {
numDigit = 0;
memset(digits, 0, sizeof digits);
if (!x) numDigit = 1;
while (x > 0) {
digits[numDigit++] = x % BASE;
x /= BASE;
}
}
Bignum& operator += (const Bignum &x) {
int carry(0);
numDigit = max(numDigit, x.numDigit);
for (int i = 0; i < numDigit; ++i) {
digits[i] += x.digits[i] + carry;
if (digits[i] >= BASE) {
digits[i] -= BASE;
carry = 1;
} else {
carry = 0;
}
}
if (carry)
digits[numDigit++] = carry;
return *this;
}
Bignum operator + (const Bignum &x) const {
Bignum res(*this);
return res += x;
}
Bignum& operator *= (int x) {
if (!x) {
*this = Bignum(0);
return *this;
}
ll remain = 0;
for (int i = 0; i < numDigit; ++i) {
remain += 1LL * digits[i] * x;
digits[i] = remain % BASE;
remain /= BASE;
}
while (remain > 0) {
digits[numDigit++] = remain % BASE;
remain /= BASE;
}
return *this;
}
Bignum operator * (int x) const {
Bignum res(*this);
res *= x;
return res;
}
ll operator % (ll x) const {
ll res(0);
for (int i = numDigit - 1; i >= 0; i--)
res = (res * BASE + digits[i]) % x;
return res;
}
#define COMPARE(a, b) (((a) > (b)) - ((a) < (b)))
int compare(const Bignum &x) const {
if (numDigit != x.numDigit) {
return COMPARE(numDigit, x.numDigit);
}
for (int i = numDigit - 1; i >= 0; --i) {
if (digits[i] != x.digits[i]) {
return COMPARE(digits[i], x.digits[i]);
}
}
return 0;
}
#define DEF_OPER(o) bool operator o (const Bignum &x) const { return compare(x) o 0; }
DEF_OPER(<) DEF_OPER(>) DEF_OPER(>=) DEF_OPER(<=) DEF_OPER(==) DEF_OPER(!=)
#undef DEF_OPER
string toString(void) const {
string res;
for (int i = 0; i < numDigit; ++i) {
int tmp = digits[i];
for (int j = 0; j < 9; ++j) {
res.push_back('0' + tmp % 10);
tmp /= 10;
}
}
while (res.size() > 1 && res.back() == '0') {
res.pop_back();
}
reverse(res.begin(), res.end());
return res;
}
};
int calc(void) {
Bignum prodNow(1);
int opt(nArr);
while(opt > 0 && prodNow <= 1e9) {
prodNow *= X[opt];
--opt;
}
while(opt > 0 && X[opt] == 1)
--opt;
ll res(1);
Bignum ans(1);
for (int i = 1; i <= opt; ++i)
res = res * X[i] % modl;
Bignum prod(1);
while(opt <= nArr) {
ans = max(ans, prod * Y[opt]);
prod *= X[++opt];
}
return res * (ans % modl) % modl;/*
int l(1), r(nArr), opt(1);
while(l <= r) {
int mid = (l + r) >> 1;
if(get(1, 1, nArr, mid, nArr) > 1e9) {
opt = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
ll prodNow(1);
for (int i = opt + 1; i <= nArr; ++i) {
prodNow *= X[i];
if(prodNow > 1e9) {
abort();
}
}
ll res = get(1, 1, nArr, 1, opt), ans(Y[opt]), prod(1);
while(opt <= nArr) {
int nxt = findFirst(segx, 1, 1, nArr, opt + 1, 2);
ans = max(ans, prod * query(segy, 1, 1, nArr, opt, nxt - 1));
prod *= X[nxt];
opt = nxt;
}
ans %= modl;
if(res * ans % modl != calc2()) {
cout << "WRONG ANSWER ! JURY: " << calc2() << ' ' << " FIND: " << res * ans % modl << '\n';
cout << nArr << '\n';
for (int i = 1; i <= nArr; ++i)
cout << X[i] << " \n"[i == nArr];
for (int i = 1; i <= nArr; ++i)
cout << Y[i] << " \n"[i == nArr];
cout << "0\n";
exit(0);
}
return res * ans % modl;*/
}
int init(int _N, int _X[], int _Y[]) {
nArr = _N;
for (int i = 1; i <= nArr; ++i) {
X[i] = _X[i - 1];
Y[i] = _Y[i - 1];
}
build(segx, 1, 1, nArr, X);
build(segy, 1, 1, nArr, Y);
for (int i = 1; i <= nArr; ++i)
modify(i, X[i]);
return calc();
}
int updateX(int pos, int val) {
++pos;
modify(pos, val);
update(segx, pos, val);
X[pos] = val;
return calc();
}
int updateY(int pos, int val) {
++pos;
Y[pos] = val;
update(segy, pos, val);
return calc();
}
