#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
const int N = 5e5 + 5, MOD = 1e9 + 7;
struct mint{
int val;
mint(long long a = 0) : val(a % MOD) {if(val < 0) val += MOD; }
mint(long long a, long long b) {*this += a, *this /= b; }
mint &operator += (const mint &b) {val += b.val; if(val >= MOD) val -= MOD; return *this; }
mint &operator -= (const mint &b) {val -= b.val; if(val < 0) val += MOD; return *this; }
mint &operator *= (const mint &b) {val = (1ll * val * b.val) % MOD; return *this; }
mint &operator /= (const mint &b) {*this *= minv(b); return *this; }
mint &operator ++ () {return *this += 1; }
mint operator ++ (int) {mint tmp = *this; *this += 1; return tmp; }
mint &operator -- () {return *this -= 1; }
mint operator -- (int) {mint tmp = *this; *this -= 1; return tmp; }
friend mint operator + (mint a, const mint &b) {return a += b; }
friend mint operator - (mint a, const mint &b) {return a -= b; }
friend mint operator - (const mint &a) {return 0 - a; }
friend mint operator * (mint a, const mint &b) {return a *= b; }
friend mint operator / (mint a, const mint &b) {return a /= b; }
friend istream &operator >> (istream &is, mint &a) {long long b; cin >> b; a = b; return is; }
friend ostream &operator << (ostream &os, const mint &a) {cout << a.val; return os; }
mint mexp(mint a, long long b){
mint c = 1;
for(; b > 0; b /= 2, a *= a) if(b & 1) c *= a;
return c;
}
mint minv(const mint &a) {return mexp(a, MOD - 2); }
};
int n, x[N], y[N];
struct SegTree{
pair<long double, int> tree[N * 4];
long double lazy[N * 4];
void push(int v){
if(lazy[v]){
tree[v].first += lazy[v];
if(v * 2 < N * 4) lazy[v * 2] += lazy[v], lazy[v * 2 + 1] += lazy[v];
lazy[v] = 0;
}
}
pair<long double, int> merge(pair<long double, int> a, pair<long double, int> b){
return max(a, b);
}
void build(int v = 1, int l = 0, int r = n - 1){
if(l == r) tree[v] = {0, l};
else{
int m = l + (r - l) / 2;
build(v * 2, l, m);
build(v * 2 + 1, m + 1, r);
tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
}
}
void update(int l, int r, long double val, int v = 1, int tl = 0, int tr = n - 1){
if(l > r) return;
else if(tl == l && tr == r) lazy[v] += val;
else{
push(v);
int tm = tl + (tr - tl) / 2;
update(l, min(r, tm), val, v * 2, tl, tm);
update(max(l, tm + 1), r, val, v * 2 + 1, tm + 1, tr);
push(v * 2), push(v * 2 + 1);
tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
}
}
int query(){
push(1);
return tree[1].second;
}
};
SegTree sgt;
struct Fenwick{
mint tree[N];
Fenwick(){
fill(tree, tree + N, mint(1));
}
mint query(int r){
mint ans = 1;
for(int i = r + 1; i > 0; i -= i & -i) ans *= tree[i];
return ans;
}
void update(int pos, mint val){
for(int i = pos + 1; i < N; i += i & -i) tree[i] *= val;
}
};
Fenwick fw;
int init(int N_, int X[], int Y[]){
n = N_;
copy(X, X + n, x);
copy(Y, Y + n, y);
sgt.build();
for(int i = 0; i < n; i++){
sgt.update(i, n - 1, log(x[i]));
sgt.update(i, i, log(y[i]));
fw.update(i, x[i]);
}
int ans = sgt.query();
return (fw.query(ans) * y[ans]).val;
}
int updateX(int pos, int val){
sgt.update(pos, n - 1, val - x[pos]);
fw.update(pos, mint(val) / x[pos]);
x[pos] = val;
int ans = sgt.query();
return (fw.query(ans) * y[ans]).val;
}
int updateY(int pos, int val){
sgt.update(pos, pos, val - y[pos]);
y[pos] = val;
int ans = sgt.query();
return (fw.query(ans) * y[ans]).val;;
}
