#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 10;
const int MX = 1e9 + 1;
const int Mod = 1e9 + 7;
ll mul(ll a, ll b){
return (a * b) % Mod;
}
ll bin_pow(ll b, ll p){
ll res = 1;
for(ll j = 1, pw = b; j <= p; j <<= 1, pw = mul(pw, pw))
if(j & p)
res = mul(res, pw);
return res;
}
ll inv(ll x){
return bin_pow(x, Mod - 2);
}
int n;
set<int> Big;
ll dp[N];
ll X[N], Y[N];
ll fen[N];
void Add(ll idx, ll x){
idx += 2;
for(; idx < N; idx += (idx & (-idx)))
fen[idx] = mul(fen[idx], x);
}
ll Get(ll idx){
if(idx < 0) return 1;
idx += 2;
ll res = 1;
for(; idx; idx -= (idx & (-idx)))
res = mul(res, fen[idx]);
return res;
}
ll seg[N << 2];
void Change(int id, int idx, ll x, int L = 0, int R = N){
if(L + 1 == R){
seg[id] = x;
return ;
}
int mid = (L + R) >> 1;
if(idx < mid)
Change(id << 1, idx, x, L, mid);
else
Change(id << 1 | 1, idx, x, mid, R);
seg[id] = max(seg[id << 1], seg[id << 1 | 1]);
}
ll Max(int id, int l, int r, int L = 0, int R = N){
if(r <= L || R <= l) return 0;
if(l <= L && R <= r) return seg[id];
int mid = (L + R) >> 1;
return max(Max(id << 1, l, r, L, mid), Max(id << 1 | 1, l, r, mid, R));
}
ll Calc(){
dp[n] = 0;
Big.insert(0);
int pos, la = n;
for(auto it = Big.rbegin(); it != Big.rend(); it ++){
pos = *it;
//for(int pos = n - 1; pos >= 0; pos --){
dp[pos] = X[pos] * max(Max(1, pos, la), dp[la]);
//dp[pos] = X[pos] * max(Y[pos], dp[la]);
//assert((X[pos] > 1 || pos == 0));
if(dp[pos] >= MX)
return mul(dp[pos] % Mod, Get(pos - 1));
la = pos;
}
return dp[0] % Mod;
}
int init(int _n, int _X[], int _Y[]) {
fill(fen, fen + N, 1);
Big.clear();
n = _n;
for(int i = 0; i < n; i++){
X[i] = _X[i]; Y[i] = _Y[i];
Change(1, i, Y[i]);
Add(i, X[i]);
if(X[i] > 1) Big.insert(i);
}
return Calc();
}
int updateX(int pos, int val) {
Big.erase(pos);
Add(pos, mul(inv(X[pos]), val) );
X[pos] = val;
if(val > 1)
Big.insert(pos);
return Calc();
}
int updateY(int pos, int val) {
Y[pos] = val;
Change(1, pos, val);
return Calc();
}
