#include <bits/stdc++.h>
using namespace std;
#define starburst ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//#define int long long
#define double long double
#define pii pair<int,int>
#define pb push_back
#define maxn 500005
#define mod 1000000007ll
#define ff first
#define ss second
int N;
vector<int> X, Y;
vector<double> lgX, lgY, PlgX;
int fastpow(int a, int b){
int ret = 1;
for(; b; b >>= 1){
if(b & 1) ret = 1ll * ret * a % mod;
a = 1ll * a * a % mod;
}
return ret;
}
struct FenwickTree{
int val[maxn];
void init(int n){
for(int i = 0; i <= n; ++i) val[i] = 1;
}
void modify(int p, int x){
for(; p < maxn; p += (p & -p)) val[p] = 1ll * x * val[p] % mod;
}
int query(int p){
int ret = 1;
for(; p; p -= (p & -p)){
ret = 1ll * ret * val[p] % mod;
}
return ret;
}
}bit;
struct SegmentTree{
pair<double, int> node[4 * maxn];
double tag[4 * maxn];
void push(int i){
double t = tag[i];
node[2 * i].ff += t, tag[2 * i] += t;
node[2 * i + 1].ff += t, tag[2 * i + 1] += t;
tag[i] = 0;
node[i] = max(node[2 * i], node[2 * i + 1]);
}
void modify(int i, int l, int r, int ql, int qr, double x){
if(l == r){
node[i].ff += x;
node[i].ss = l;
return;
}
push(i);
if(ql <= l && r <= qr){
node[i].ff += x;
tag[i] += x;
return;
}
int mid = (l + r) / 2;
if(ql <= mid) modify(2 * i, l, mid, ql, qr, x);
if(mid < qr) modify(2 * i + 1, mid + 1, r, ql, qr, x);
node[i] = max(node[2 * i], node[2 * i + 1]);
}
}seg;
int init(int n, int *x, int *y){
N = n;
bit.init(N + 1);
X.assign(N + 1, 0), Y.assign(N + 1, 0);
lgX.assign(N + 1, 0.0), lgY.assign(N + 1, 0.0), PlgX.assign(N + 1, 0.0);
for(int i = 1; i <= n; ++i){
X[i] = x[i - 1], Y[i] = y[i - 1];
lgX[i] = log(X[i]), lgY[i] = log(Y[i]);
PlgX[i] = PlgX[i - 1] + lgX[i];
bit.modify(i, X[i]);
seg.modify(1, 1, N, i, i, PlgX[i] + lgY[i]);
}
int id = seg.node[1].ss;
int BX = bit.query(id);
return 1ll * BX * Y[id] % mod;
}
int updateX(int pos, int val){
pos++;
bit.modify(pos, fastpow(X[pos], mod - 2));
bit.modify(pos, val);
seg.modify(1, 1, N, pos, N, -lgX[pos]);
X[pos] = val;
lgX[pos] = log(val);
seg.modify(1, 1, N, pos, N, lgX[pos]);
int id = seg.node[1].ss;
int BX = bit.query(id);
return 1ll * BX * Y[id] % mod;
}
int updateY(int pos, int val){
pos++;
seg.modify(1, 1, N, pos, pos, -lgY[pos]);
Y[pos] = val;
lgY[pos] = log(val);
seg.modify(1, 1, N, pos, pos, lgY[pos]);
int id = seg.node[1].ss;
int BX = bit.query(id);
return 1ll * BX * Y[id] % mod;
}
