#include "horses.h"
#include <vector>
#include <algorithm>
#include <cstdio>
#define MAX 50000
#define ll long long
#define lft 2 * v
#define rht (2 * v) + 1
ll MOD = 1e9 + 7;
using namespace std;
ll n;
ll y[MAX];
ll x[MAX];
vector<ll> seg_prod(MAX * 4);
vector<ll> seg_prod_max(MAX * 4);
vector<ll> seg_y(MAX * 4);
void build(ll v, ll tl, ll tr) {
if (tl == tr) {
seg_prod[v] = x[tl];
seg_prod_max[v] = x[tl];
} else {
ll mid = (tl + tr) / 2;
build(lft, tl, mid);
build(rht, mid + 1, tr);
ll prod = seg_prod[lft] * seg_prod[rht];
seg_prod[v] = prod % MOD;
seg_prod_max[v] = min(prod, MOD);
}
}
void update(ll v, ll idx, ll tl, ll tr) {
if (tl > tr) return;
if (tl == idx && tl == tr) {
seg_prod[v] = x[idx];
seg_prod_max[v] = x[idx];
return;
}
ll mid = (tl + tr) / 2;
if (idx > mid) update(rht, idx, mid + 1, tr);
else update(lft, idx, tl, mid);
ll prod = seg_prod[lft] * seg_prod[rht];
seg_prod[v] = prod % MOD;
seg_prod_max[v] = min(prod, MOD);
}
ll query1(ll v, ll l, ll r, ll tl, ll tr) {
if (l > r) return 1;
if (tl == l && tr == r) return seg_prod[v];
ll mid = (tl + tr) / 2;
ll ret = query1(lft, l, min(r, mid), tl, mid) *
query1(rht, max(l, mid + 1), r, mid + 1, tr);
return ret % MOD;
}
ll query2(ll v, ll l, ll r, ll tl, ll tr) {
if (l > r) return 1;
if (tl == l && tr == r) return seg_prod_max[v];
ll mid = (tl + tr) / 2;
ll ret = query2(lft, l, min(r, mid), tl, mid) *
query2(rht, max(l, mid + 1), r, mid + 1, tr);
return min(MOD, ret);
}
void build_y(ll v, ll tl, ll tr) {
if (tl == tr) seg_y[v] = tl;
else {
ll mid = (tl + tr) / 2;
build_y(lft, tl, mid);
build_y(rht, mid + 1, tr);
ll left = seg_y[lft];
ll right = seg_y[rht];
ll p1 = y[left]; ll p2 = query2(1, left + 1, right, 0, n - 1);
if (p2 > p1) seg_y[v] = right;
else seg_y[v] = left;
}
}
void update_y(ll v, ll idx, ll tl, ll tr) {
if (tl == tr && tl == idx) {
seg_y[v] = y[idx];
return;
}
ll mid = (tl + tr) / 2;
if (idx > mid) update_y(rht, idx, mid + 1, tr);
else update_y(lft, idx, tl, mid - 1);
ll left = seg_y[lft];
ll right = seg_y[rht];
ll p1 = y[left]; ll p2 = query2(1, left + 1, right, 0, n - 1);
if (p2 > p1) seg_y[v] = right;
else seg_y[v] = left;
}
ll find(ll idx) {
return (query1(1, 0, idx, 0, n - 1) * y[idx]) % MOD;
}
int init(int N, int X[], int Y[]) {
n = (ll)N;
for (ll i = 0; i < n; ++i) y[i] = (ll)Y[i];
for (ll i = 0; i < n; ++i) x[i] = (ll)X[i];
build(1, 0, n - 1);
build_y(1, 0, n - 1);
return find(seg_y[1]);
}
int updateX(int pos, int val) {
return 12781;
}
int updateY(int pos, int val) {
return 17163;
}
