#include <iostream>
#include <set>
#include "horses.h"
using namespace std;
#define ll long long
const int N = 1<<17;
int X[N<<2], Mx[N<<1];
ll prd, mod = 1e9 + 7;
set<int> st;
void insert(int i, int vl, int cur = 1, int st = 1, int en = N){
if (i >= en or i < st)
return;
if (en - st == 1){
Mx[cur] = vl;
return;
}
int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
insert(i, vl, lc, st, mid);
insert(i, vl, rc, mid, en);
Mx[cur] = max(Mx[lc], Mx[rc]);
}
int get(int l, int r, int cur = 1, int st = 1, int en = N){
if (l >= en or r <= st)
return 0;
if (l <= st and r >= en)
return Mx[cur];
int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
return max(get(l, r, lc, st, mid), get(l, r, rc, mid, en));
}
int power(int a, int b){
if (b == 1)
return a;
ll ans = power(a, b / 2);
ans = ans * ans % mod;
if (b % 2)
ans = ans * a % mod;
return ans;
}
int Answer(){
ll pd = prd, lst = N, sufMax = 0;
auto it = st.end();
while (it != begin(st)){
it = prev(it);
pd = pd * power(X[*it], mod - 2) % mod;
sufMax = max(sufMax, (ll)get(*it, lst)) * X[*it];
if (sufMax > mod)
return sufMax % mod * pd;
lst = *it;
}
return sufMax % mod;
}
int init(int n, int x[], int y[]){
prd = 1;
for (int i=1;i<=n;i++){
X[i] = x[i-1];
prd = prd * X[i] % mod;
insert(i, y[i-1]);
if (x[i-1] > 1 or i == 1)
st.insert(i);
}
return Answer();
}
int updateX(int id, int val){
id++;
if (X[id] > 1 or id == 1)
st.erase(id);
prd = prd * val % mod * power(X[id], mod - 2) % mod;
X[id] = val;
if (X[id] > 1 or id == 1)
st.insert(id);
return Answer();
}
int updateY(int id, int val){
id++;
insert(id, val);
return Answer();
}
