#include "horses.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<set>
typedef long long ll;
using namespace std;
namespace{
int n;
vector<int> seg;
void build(int l, int r, int ind, vector<ll>& vec){
if(l == r){
seg[ind] = vec[l];
return;
}
int mid = (l + r) >> 1;
build(l, mid, ind * 2, vec);
build(mid + 1, r, ind * 2 + 1, vec);
seg[ind] = max(seg[ind * 2], seg[ind * 2 + 1]);
}
void modify(int l, int r, int num, int pos, int ind){
if(l == r){
seg[ind] = num;
return;
}
int mid = (l + r) >> 1;
if(pos <= mid) modify(l, mid, num, pos, ind * 2);
else modify(mid + 1, r, num, pos, ind * 2 + 1);
seg[ind] = max(seg[ind * 2], seg[ind * 2 + 1]);
}
int query(int l, int r, int start, int end, int ind){
if(r < start || end < l) return 0;
if(start <= l && r <= end) return seg[ind];
int mid = (l + r) >> 1;
return max(query(l, mid, start, end, ind * 2), query(mid + 1, r, start, end, ind * 2 + 1));
}
const ll mod = 1e9 + 7;
ll power(ll a, ll b){
if(b == 1) return a % mod;
if(b & 1) return power(a, b - 1) * a % mod;
ll tmp = power(a, b / 2);
return tmp * tmp % mod;
}
ll inverse(ll a){
return power(a, mod - 2);
}
vector<ll> x, y;
set<int> s;
ll prod = 1;
}
int init(int N, int X[], int Y[]) {
n = N;
x.resize(n + 1);
y.resize(n + 1);
seg.resize(4 * n + 4);
for(int i = 1; i <= n; i++) x[i] = X[i - 1], y[i] = Y[i - 1];
build(1, n, 1, y);
for(int i = 1; i <= n; i++) if(x[i] > 1) s.insert(i);
for(int i = 1; i <= n; i++) prod = prod * x[i] % mod;
if((int)s.size() == 0){
return seg[1];
}
auto iter = prev(s.end());
ll cur = 1;
int curpos;
vector<int> poss;
while(1){
curpos = (*iter);
poss.push_back(curpos);
cur *= x[curpos];
if(cur > mod) break;
if(iter == s.begin()){
if(curpos != 1) poss.push_back(1);
break;
}
iter = prev(iter);
}
reverse(poss.begin(), poss.end());
__int128_t maxi = 1, now = 1;
int sz = poss.size();
for(int i = 0; i < sz; i++){
now *= x[poss[i]];
if(i == sz - 1) maxi = max(maxi, now * query(1, n, poss[i], n, 1));
else maxi = max(maxi, now * query(1, n, poss[i], poss[i + 1] - 1, 1));
}
return maxi % mod * inverse(now % mod) % mod * prod % mod;
}
int updateX(int pos, int val) {
pos++;
if(x[pos] > 1) s.erase(pos);
prod *= inverse(x[pos]);
prod %= mod;
x[pos] = val;
prod *= val;
prod %= mod;
if(x[pos] > 1) s.insert(pos);
if((int)s.size() == 0){
return seg[1];
}
auto iter = prev(s.end());
ll cur = 1;
int curpos;
vector<int> poss;
while(1){
curpos = (*iter);
poss.push_back(curpos);
cur *= x[curpos];
if(cur > mod) break;
if(iter == s.begin()){
if(curpos != 1) poss.push_back(1);
break;
}
iter = prev(iter);
}
reverse(poss.begin(), poss.end());
__int128_t maxi = 1, now = 1;
int sz = poss.size();
for(int i = 0; i < sz; i++){
now *= x[poss[i]];
if(i == sz - 1) maxi = max(maxi, now * query(1, n, poss[i], n, 1));
else maxi = max(maxi, now * query(1, n, poss[i], poss[i + 1] - 1, 1));
}
return maxi % mod * inverse(now % mod) % mod * prod % mod;
}
int updateY(int pos, int val) {
pos++;
modify(1, n, val, pos, 1);
y[pos] = val;
if((int)s.size() == 0){
return seg[1];
}
auto iter = prev(s.end());
ll cur = 1;
int curpos;
vector<int> poss;
while(1){
curpos = (*iter);
poss.push_back(curpos);
cur *= x[curpos];
if(cur > mod) break;
if(iter == s.begin()){
if(curpos != 1) poss.push_back(1);
break;
}
iter = prev(iter);
}
reverse(poss.begin(), poss.end());
__int128_t maxi = 1, now = 1;
int sz = poss.size();
for(int i = 0; i < sz; i++){
now *= x[poss[i]];
if(i == sz - 1) maxi = max(maxi, now * query(1, n, poss[i], n, 1));
else maxi = max(maxi, now * query(1, n, poss[i], poss[i + 1] - 1, 1));
}
return maxi % mod * inverse(now % mod) % mod * prod % mod;
}
// g++ -std=c++17 -Wall -Wextra -fsanitize=undefined -fsanitize=address -Wshadow -o run horses.cpp grader.cpp
