#include "horses.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, ll>
using namespace std;
const int MOD = 1e9 + 7;
const ll oo = 1e9 + 9;
const int MAX = 5e5 + 5;
struct DATA{
int index, leftMultipliyer, rightMultiplier;
};
int n;
int price[MAX], cnt[MAX];
DATA tree[MAX * 4];
DATA merge(DATA a, DATA b){
ll m = min(oo, 1ll * a.rightMultiplier * b.leftMultipliyer);
if(price[a.index] / m >= price[b.index]){
return {a.index, a.leftMultipliyer, min(oo, m * b.rightMultiplier)};
}
else{
return {b.index, min(oo, m * a.leftMultipliyer), b.rightMultiplier};
}
}
void build(int node, int l, int r){
if(l == r){
tree[node] = {l, cnt[l], 1};
return;
}
int mid = (l + r) / 2;
build(node << 1 | 1, l, mid);
build((node + 1) << 1, mid + 1, r);
tree[node] = merge(tree[(node << 1) | 1], tree[(node + 1) << 1]);
}
void update(int node, int l, int r, int pos, int val){
if(l == r){
tree[node] = {l, cnt[l], 1};
return;
}
int mid = (l + r) / 2;
if(pos <= mid){
update((node << 1) + 1, l, mid, pos, val);
}
else{
update((node + 1) << 1, mid + 1, r, pos, val);
}
tree[node] = merge(tree[(node << 1) | 1], tree[(node + 1) << 1]);
}
int tree1[MAX * 4];
void build2(int node, int l, int r){
if(l == r){
tree1[node] = cnt[l];
return;
}
int mid = (l + r) / 2;
build2((node << 1) + 1, l, mid);
build2((node + 1) << 1, mid + 1, r);
tree1[node] = (1ll * tree1[(node << 1) + 1] * tree1[(node + 1) << 1]) % MOD;
}
void update2(int node, int l, int r, int pos, int val){
if(l == r){
tree1[node] = val;
return;
}
int mid = (l + r) / 2;
if(pos <= mid){
update2((node << 1) + 1, l, mid, pos, val);
}
else{
update2((node + 1) << 1, mid + 1, r, pos, val);
}
tree1[node] = (1ll * tree1[(node << 1) + 1] * tree1[(node + 1) << 1]) % MOD;
}
int ask2(int node, int l, int r, int ql, int qr){
if(qr < l || ql > r){
return 1;
}
if(ql <= l && r <= qr){
return tree1[node];
}
int mid = (l + r) / 2;
return (1ll * ask2((node << 1) + 1, l, mid, ql, qr) * ask2((node + 1) << 1, mid + 1, r, ql, qr)) % MOD;
}
int calcAns(){
DATA ans = tree[0];
return 1ll * ask2(0, 0, n - 1, 0, ans.index) * price[ans.index] % MOD;
}
int init(int N, int X[], int Y[]) {
n = N;
for (int i = 0; i < n; i++)
{
cnt[i] = X[i];
price[i] = Y[i];
}
build(0, 0, n - 1);
build2(0, 0, n - 1);
return calcAns();
}
int updateX(int pos, int val) {
cnt[pos] = val;
update(0, 0, n - 1, pos, cnt[pos]);
update2(0, 0, n - 1, pos, val);
return calcAns();
}
int updateY(int pos, int val) {
price[pos] = val;
update(0, 0, n - 1, pos, cnt[pos]);
return calcAns();
}
