#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
typedef long double ld;
#define fi first
#define se second
ll mod = 1e9 + 7;
vector<pair<ll, ld>> st;
vector<pair<ll, ld>> lz;
vector<ll> x;
vector<ll> y;
int n;
int len = 1;
ll pow(ll n, ll k){
n %= mod;
ll res = 1;
while(k > 0){
if(k % 2) res = res * n % mod;
k /= 2;
n = n * n % mod;
}
return res;
}
ll modInv(ll x){
return pow(x, mod - 2);
}
void prop(int i){
st[i * 2].fi = st[i * 2].fi * lz[i].fi % mod;
st[i * 2].se += lz[i].se;
lz[i * 2].fi = lz[i * 2].fi * lz[i].fi % mod;
lz[i * 2].se += lz[i].se;
st[i * 2 + 1].fi = st[i * 2 + 1].fi * lz[i].fi % mod;
st[i * 2 + 1].se += lz[i].se;
lz[i * 2 + 1].fi = lz[i * 2 + 1].fi * lz[i].fi % mod;
lz[i * 2 + 1].se += lz[i].se;
}
void upd(int l, int r, ll mval, ld lval, int i = 1, int s = 0, int e = len){
if(l >= e || s >= r) return;
if(l <= s && e <= r){
st[i].fi = st[i].fi * mval % mod;
st[i].se += lval;
lz[i].fi = lz[i].fi * mval % mod;
lz[i].se += lval;
return;
}
prop(i);
upd(l, r, mval, lval, i * 2, s, (s + e) / 2);
upd(l, r, mval, lval, i * 2 + 1, (s + e) / 2, e);
if(st[i * 2].second > st[i * 2 + 1].second){
st[i] = st[i * 2];
}
else st[i] = st[i * 2 + 1];
}
int init(int N, int X[], int Y[]) {
x.assign(X, X + N);
y.assign(Y, Y + N);
n = N;
while(len < N) len *= 2;
st.resize(2 * len, {1, 0});
lz.resize(2 * len, {1, 0});
for (int i = 0; i < N; i++) {
st[len + i].fi = st[len + i - 1].fi * x[i] % mod;
st[len + i].second = st[len + i - 1].se + logl(x[i]);
}
for (int i = 0; i < N; i++) {
st[len + i].fi = st[len + i].fi * y[i] % mod;
st[len + i].se += logl(y[i]);
}
for (int i = len - 1; i > 0; i--) {
if(st[i * 2].second > st[i * 2 + 1].second){
st[i] = st[i * 2];
}
else st[i] = st[i * 2 + 1];
}
return st[1].first;
}
int updateX(int pos, int val) {
upd(pos, len + 1, val * modInv(x[pos]) % mod, logl(val) - logl(x[pos]));
x[pos] = val;
return st[1].first;
}
int updateY(int pos, int val) {
upd(pos, pos + 1, val * modInv(y[pos]) % mod, logl(val) - logl(y[pos]));
y[pos] = val;
return st[1].first;
}
