#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
typedef long long ll;
const int N = 5e5 + 10;
const int mod = 1e9 + 7;
long double mx[N << 2], a[N], add[N << 2];
int prod[N << 2], mul[N << 2], opt[N << 2];
int x[N], y[N], n, p[N];
int Pow(int n, int p) {
int ret = 1;
while(p) {
if(p & 1) ret = (ll) ret * n % mod;
n = (ll) n * n % mod;
p >>= 1;
} return ret;
}
void merge(int node) {
long double a = mx[node << 1], b = mx[node << 1 | 1];
if(b - a >= 1e-9) mx[node] = b, opt[node] = opt[node << 1 | 1];
else mx[node] = a, opt[node] = opt[node << 1];
prod[node] = (ll) prod[node << 1] * prod[node << 1 | 1] % mod;
}
void build(int node, int l, int r) {
add[node] = 0, mul[node] = 1;
if(l == r) {
mx[node] = a[l];
prod[node] = p[l];
opt[node] = l;
return;
} int m = l + r >> 1;
build(node << 1, l, m);
build(node << 1 | 1, m + 1, r);
merge(node);
}
void upd(int node, long double A, int B) {
mx[node] += A;
prod[node] = (ll) prod[node] * B % mod;
}
void shift(int node) {
if(!add[node] && mul[node] == 1) return;
upd(node << 1, add[node], mul[node]);
upd(node << 1 | 1, add[node], mul[node]);
add[node] = 0, mul[node] = 1;
}
void update(int node, int l, int r, int i, int j, long double A, int B) {
if(r < i || l > j) return;
if(i <= l && r <= j) {
upd(node, A, B);
return;
} shift(node);
int m = l + r >> 1;
update(node << 1, l, m, i, j, A, B);
update(node << 1 | 1, m + 1, r, i, j, A, B);
merge(node);
}
int query(int node, int l, int r, int i) {
if(l == r) return prod[node];
shift(node);
int m = l + r >> 1;
if(i <= m) return query(node << 1, l, m, i);
else return query(node << 1 | 1, m + 1, r, i);
}
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];
p[0] = x[0]; a[0] = log(x[0]) + log(y[0]);
for(int i = 1; i < N; i++) {
p[i] = (ll) p[i - 1] * x[i] % mod;
a[i] = a[i - 1] - log(y[i - 1]) + log(y[i]) + log(x[i]);
}
build(1, 0, N - 1);
int ans = (ll) query(1, 0, n - 1, opt[1]) * y[opt[1]] % mod;
return ans;
}
int updateX(int pos, int val) {
update(1, 0, n - 1, pos, n - 1, log(val) - log(x[pos]), (ll) val * Pow(x[pos], mod - 2) % mod);
x[pos] = val;
int ans = (ll) query(1, 0, n - 1, opt[1]) * y[opt[1]] % mod;
return ans;
}
int updateY(int pos, int val) {
update(1, 0, n - 1, pos, pos, log(val) - log(y[pos]), (ll) val * Pow(y[pos], mod - 2) % mod);
y[pos] = val;
int ans = (ll) query(1, 0, n - 1, opt[1]) * y[opt[1]] % mod;
return ans;
}
