#include<bits/stdc++.h>
#include "horses.h"
using namespace std;
#define ll long long
#define int 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){
if (y == 1){
return x;
}
int res = my_pow(x, y / 2) % MOD;
int b = 1;
if (y % 2){
b = y;
}
return ((res * res) % MOD * b) % MOD;
}
int my_div(int x){
return my_pow(x, MOD - 2);
}
// void update(int x, int l, int r, int pos, int val){ // pos da find const ari querize
// if (l == r){
// tree[x] = val;
// return;
// }
// // orobiti dzebna
// int mid = (l + r) / 2;
// if (pos <= mid){ // marcxniv
// update(2 * x, l, mid, pos, val);
// }else{
// update(2 * x + 1, mid + 1, r, pos, val);
// }
// tree[x] = max(tree[2 * x], tree[2 * x + 1]); // tree[2x] da tree[2x + 1] ukve datvlili gveqneba recursiis gamo
// }
// int get(int x, int l, int r, int tl, int tr){ // query const: tl, tr
// if (tl <= l && r <= tr){
// return tree[x];
// }
// int mid = (l + r) / 2;
// int ans = 0;
// if (tl <= mid){ // marcxniv
// ans = get(2 * x, l, mid, tl, tr);
// }
// if (mid + 1 <= tr){ // marjvniv
// ans = max(ans, get(2 * x + 1, mid + 1, r, tl, tr));
// }
// return ans;
// }
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){
int ans = 0, ansi = 0, pre = 1;
for (int i = 0; i < x.size(); i++){
pre *= x[i];
if (ans < pre * y[i]){
ans = pre * y[i];
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){
suf *= (*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));
int r = my_func(x1, y1);
int ans = namr;
for (int i = r + 1; i < x1.size(); i++){
ans *= my_div(a[x1[i]]);
}
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 = namr * my_div(a[pos]);
namr *= val;
a[pos] = val;
return solve();
}
int updateY(int pos, int val) {
update(0, 0, n - 1, pos, val);
return solve();
}
