#include "horses.h"
#include <bits/stdc++.h>
#define printv(a, b) { \
for(auto pv : a) b << pv << " "; \
b << "\n"; \
}
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
struct SegmentTree{
vector<int> st;
void modify(int pos, int v, int L, int R, int id){
if(L == R){
st[id] = v;
return;
}
int M = (L + R) / 2;
if(pos <= M) modify(pos, v, L, M, 2 * id + 1);
else modify(pos, v, M + 1, R, 2 * id + 2);
st[id] = max(st[2 * id + 1], st[2 * id + 2]);
}
int query(int l, int r, int L, int R, int id){
if(l == L && r == R){
return st[id];
}
int M = (L + R) / 2;
if(r <= M) return query(l, r, L, M, 2 * id + 1);
else if(l > M) return query(l, r, M + 1, R, 2 * id + 2);
else return max(query(l, M, L, M, 2 * id + 1), query(M + 1, r, M + 1, R, 2 * id + 2));
}
};
struct BIT{
vector<ll> bit;
int lowbit(int x){
return x & -x;
}
void modify(int x, ll v){
x++;
for(; x < bit.size(); x += lowbit(x)){
bit[x] = bit[x] * v % MOD;
}
}
ll query(int x){
x++;
ll ans = 1;
for(; x > 0; x -= lowbit(x)){
ans = ans * bit[x] % MOD;
}
return ans;
}
};
ll inv(ll a){
ll b = MOD - 2;
ll ans = 1;
while(b > 0){
if(b & 1) ans = ans * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return ans;
}
SegmentTree st;
BIT bit;
int n;
vector<int> x, y;
set<int> large;
ll calc(){
//cerr << "test\n";
//printv(large, cerr);
int now = n;
ll ans = 0;
int cnt = 0;
while(ans <= 1000000000 && now >= 0){
//cerr << now << " " << ans << "\n";
ans = ans * x[now];
auto it = large.lower_bound(now);
int nxt;
if(it == large.begin()) nxt = 0;
else nxt = *prev(it) + 1;
//cerr << nxt << "\n";
ans = max(ans, (ll)st.query(nxt, now, 0, n, 0));
now = nxt - 1;
}
ans %= MOD;
//printv(x, cerr);
//printv(bit.bit, cerr);
if(now >= 0) ans = ans * bit.query(now) % MOD;
//cerr << "ok " << now << " " << ans << "\n";
return ans;
}
void qq(){
st.st.clear();
bit.bit.clear();
large.clear();
st.st.resize(4 * (n + 1));
bit.bit.resize(n + 1, 1);
x[n] = 1;
for(int i = 0; i < n; i++){
st.modify(i + 1, y[i + 1], 0, n, 0);
bit.modify(i, x[i]);
if(x[i] >= 2) large.insert(i);
}
}
int init(int N, int X[], int Y[]){
n = N;
x.resize(n + 1);
y.resize(n + 1);
for(int i = 0; i < n; i++){
x[i] = X[i];
y[i + 1] = Y[i];
}
qq();
ll ans = calc();
//printv(x, cerr);
//printv(y, cerr);
return ans;
}
int updateX(int pos, int val){
if(x[pos] >= 2) large.erase(pos);
bit.modify(pos, inv(x[pos]) * val % MOD);
x[pos] = val;
if(val >= 2) large.insert(pos);
return calc();
}
int updateY(int pos, int val){
pos++;
y[pos] = val;
st.modify(pos, val, 0, n, 0);
return calc();
}
