#include <bits/stdc++.h>
// mrrrow meeow :3
// go play vivid/stasis now! it's free on steam
#define fo(i, a, b) for (auto i = (a); i < (b); i++)
#define of(i, a, b) for (auto i = (b); i-- > (a);)
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define be(a) a.begin(), a.end()
using namespace std;
int ____init = [] {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
return 0;
}();
struct BigInt {
int v;
bool too_big;
BigInt(int v) : v(v % 1000000007), too_big(v >= 1000000007) {}
BigInt operator*(BigInt const &other) {
BigInt res((long long)v * other.v % 1000000007);
res.too_big = too_big ? true : v == 0 ? false : other.too_big ? true : other.v == 0 ? false : (long long)v * other.v >= 1000000007;
return res;
}
bool operator>(BigInt const &other) {
return too_big == other.too_big ? v > other.v : too_big > other.too_big;
}
};
struct SegTree {
BigInt xl, xr, y;
SegTree() : xl(1), xr(1), y(0) {}
SegTree combine(SegTree &r) {
SegTree &l = *this;
SegTree res;
if (l.y > l.xr * r.xl * r.y) {
res.xl = l.xl;
res.xr = l.xr * r.xl * r.xr;
res.y = l.y;
} else {
res.xl = l.xl * l.xr * r.xl;
res.xr = r.xr;
res.y = r.y;
}
return res;
}
};
const int N = 1 << 19;
SegTree st[N * 2];
int init(int n, int x[], int y[]) {
fo(i, 0, n) st[N + i].xl = BigInt(x[i]), st[N + i].y = BigInt(y[i]);
of(i, 1, N) st[i] = st[i * 2].combine(st[i * 2 + 1]);
return (st[1].xl * st[1].y).v;
}
int updateX(int pos, int val) {
st[N + pos].xl = BigInt(val);
for (int i = (N + pos) / 2; i > 0; i /= 2) st[i] = st[i * 2].combine(st[i * 2 + 1]);
return (st[1].xl * st[1].y).v;
}
int updateY(int pos, int val) {
st[N + pos].y = BigInt(val);
for (int i = (N + pos) / 2; i > 0; i /= 2) st[i] = st[i * 2].combine(st[i * 2 + 1]);
return (st[1].xl * st[1].y).v;
}
