#include<bits/stdc++.h>
// #include "horses.h"
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
const int N = 5e2 + 5;
const int MOD = 1e9 + 7;
int tree[4 * N + 1];
int a[N], b[N];
int namr = 1, n = 0;
set<int> s;
int my_pow(int x, int y){
// iterative fast power (modular)
int64_t base = (x % MOD + MOD) % MOD;
int64_t res = 1;
int64_t exp = y;
while (exp > 0) {
if (exp & 1) res = (res * base) % MOD;
base = (base * base) % MOD;
exp >>= 1;
}
return (int)res;
}
int my_div(int x){
return my_pow(x, MOD - 2);
}
void update(int x, int l, int r, int pos, int val){
b[pos] = val;
}
int get(int x, int l, int r, int tl, int tr){
int ma = 0;
for (int i = tl; i <= tr; i++){
ma = max(ma, b[i]);
}
return ma;
}
int my_func(vector<int> x, vector<int> y){
// x contains values (not positions). Use __int128 for safe product/comparison.
__int128 pre = 1;
__int128 best = 0;
int ansi = 0;
for (int i = 0; i < (int)x.size(); i++){
pre *= (__int128)x[i];
__int128 cand = pre * (__int128)y[i];
if (cand > best){
best = cand;
ansi = i;
}
}
return ansi;
}
int init(int n1, int x[], int y[]) {
n = n1;
for (int i = 0; i < n; i++){
if (x[i] != 1){
s.insert(i);
}
}
for (int i = 0; i < n; i++){
update(0, 0, n - 1, i, y[i]);
}
for (int i = 0; i < n; i++){
a[i] = x[i];
b[i] = y[i];
}
// mtlianis namr
for (int i = 0; i < n; i++){
namr *= x[i];
namr %= MOD;
}
return 0;
}
int solve(){
vector<int> x1, y1;
auto it = s.end();
it--;
int suf = 1;
while (suf < 1e9){
// BUG FIX: multiply by value a[*it], not by the index *it
suf *= a[*it];
x1.pb(*it);
if (it == s.begin()){
break;
}
it--;
}
reverse(x1.begin(), x1.end());
for (int i = 0; i < x1.size() - 1; i++){
y1.pb(get(0, 0, n - 1, x1[i], x1[i + 1] - 1));
}
// (*x.rbegin(), n);
y1.pb(get(0, 0, n - 1, (*x1.rbegin()), n - 1));
// BUG FIX: my_func expects the a[] values, not positions.
vector<int> vals;
for (int pos : x1) vals.pb(a[pos]);
int r = my_func(vals, y1);
int ans = namr;
for (int i = r + 1; i < x1.size(); i++){
ans = ( (long long)ans * my_div(a[x1[i]]) ) % MOD;
}
if (ans < 0) ans += MOD;
return ans;
}
int updateX(int pos, int val) {
if (s.count(pos) && val == 1){
s.erase(pos);
}else if (!s.count(pos) && val != 1){
s.insert(pos);
}
// namr-is shecvla
namr = ( (long long)namr * my_div(a[pos]) ) % MOD;
namr = ( (long long)namr * (val % MOD) ) % MOD;
a[pos] = val;
a[pos] = val;
return solve();
}
int updateY(int pos, int val) {
update(0, 0, n - 1, pos, val);
return solve();
}
