#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007LL;
const long double INF = 1e30L;
int n;
vector<int> xval;
vector<int> yval;
vector<long double> bit;
vector<long double> segmx;
vector<long double> lazy;
vector<int> segidx;
vector<long long> segprod;
void addbit(int idx, long double val){
idx++;
while(idx <= n){
bit[idx] += val;
idx += idx & -idx;
}
}
long double getbit(int idx){
idx++;
long double res = 0;
while(idx > 0){
res += bit[idx];
idx -= idx & -idx;
}
return res;
}
long long modpow(long long a, long long e){
long long res = 1;
while(e > 0){
if(e & 1){
res = res * a % MOD;
}
a = a * a % MOD;
e >>= 1;
}
return res;
}
void pull(int node){
if(segmx[node * 2] >= segmx[node * 2 + 1]){
segmx[node] = segmx[node * 2];
segidx[node] = segidx[node * 2];
}
else{
segmx[node] = segmx[node * 2 + 1];
segidx[node] = segidx[node * 2 + 1];
}
segprod[node] = segprod[node * 2] * segprod[node * 2 + 1] % MOD;
}
void apply(int node, long double val){
segmx[node] += val;
lazy[node] += val;
}
void push(int node){
if(lazy[node] != 0){
apply(node * 2, lazy[node]);
apply(node * 2 + 1, lazy[node]);
lazy[node] = 0;
}
}
void build(int node, int l, int r, vector<long double> &base){
if(l == r){
segmx[node] = base[l];
segidx[node] = l;
segprod[node] = xval[l];
return;
}
int mid = (l + r) / 2;
build(node * 2, l, mid, base);
build(node * 2 + 1, mid + 1, r, base);
pull(node);
}
void range_add(int node, int l, int r, int ql, int qr, long double val){
if(ql <= l && r <= qr){
apply(node, val);
return;
}
push(node);
int mid = (l + r) / 2;
if(ql <= mid){
range_add(node * 2, l, mid, ql, qr, val);
}
if(qr > mid){
range_add(node * 2 + 1, mid + 1, r, ql, qr, val);
}
pull(node);
}
void point_set(int node, int l, int r, int pos, long double val){
if(l == r){
segmx[node] = val;
segidx[node] = l;
return;
}
push(node);
int mid = (l + r) / 2;
if(pos <= mid){
point_set(node * 2, l, mid, pos, val);
}
else{
point_set(node * 2 + 1, mid + 1, r, pos, val);
}
pull(node);
}
void prod_update(int node, int l, int r, int pos, long long val){
if(l == r){
segprod[node] = val;
return;
}
int mid = (l + r) / 2;
if(pos <= mid){
prod_update(node * 2, l, mid, pos, val);
}
else{
prod_update(node * 2 + 1, mid + 1, r, pos, val);
}
segprod[node] = segprod[node * 2] * segprod[node * 2 + 1] % MOD;
}
long long prod_query(int node, int l, int r, int ql, int qr){
if(ql <= l && r <= qr){
return segprod[node];
}
int mid = (l + r) / 2;
if(qr <= mid){
return prod_query(node * 2, l, mid, ql, qr);
}
if(ql > mid){
return prod_query(node * 2 + 1, mid + 1, r, ql, qr);
}
return prod_query(node * 2, l, mid, ql, qr) * prod_query(node * 2 + 1, mid + 1, r, ql, qr) % MOD;
}
int get_answer(){
int idx = segidx[1];
long long pref = prod_query(1, 0, n - 1, 0, idx);
long long ans = pref * (long long)yval[idx] % MOD;
return (int)ans;
}
int init(int N, int X[], int Y[]){
n = N;
xval.assign(n, 0);
yval.assign(n, 0);
bit.assign(n + 1, 0);
segmx.assign(4 * n + 5, 0);
lazy.assign(4 * n + 5, 0);
segidx.assign(4 * n + 5, 0);
segprod.assign(4 * n + 5, 1);
vector<long double> base(n);
long double cur = 0;
for(int i = 0; i < n; i++){
xval[i] = X[i];
yval[i] = Y[i];
addbit(i, log((long double)xval[i]));
cur += log((long double)xval[i]);
base[i] = cur + log((long double)yval[i]);
}
build(1, 0, n - 1, base);
return get_answer();
}
int updateX(int pos, int val){
long double oldlog = log((long double)xval[pos]);
long double newlog = log((long double)val);
long double delta = newlog - oldlog;
xval[pos] = val;
addbit(pos, delta);
range_add(1, 0, n - 1, pos, n - 1, delta);
prod_update(1, 0, n - 1, pos, val);
return get_answer();
}
int updateY(int pos, int val){
yval[pos] = val;
long double pref = getbit(pos);
point_set(1, 0, n - 1, pos, pref + log((long double)val));
return get_answer();
}
