//#include "grader.cpp"
#include "horses.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
using namespace __gnu_pbds;
#define pb push_back
#define all(x) x.begin(),x.end()
#define ar array
#define mrand(a, b) uniform_int_distribution<int>(a, b)(rng)
template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}
template<class T> using ste = tree<T, null_type, less_equal<T>,
rb_tree_tag, tree_order_statistics_node_update>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const long long inf = 1e17 + 7;
const int mod = 1e9 + 7;
const int N = 5e5 + 5;
const int md = 998244353;
int binpow(int a, int b, int m){
if(b == 0)return 1;
if(b % 2 == 0){
int c = binpow(a,b/2,m);
return (c*c)%m;
}
return (binpow(a,b-1,m)*a)%m;
}
int divi(int a, int b, int m){
return (a*(binpow(b,m-2, m)))%m;
}
vector<int>a(N), b(N);
int n;
long long t[N*4];
int mxi[N*4], cnt[N*4];
void update(int tl, int tr, int v, int pos, int val){
if(tl == tr){
t[v] = val;
return;
}
int tm = (tl + tr) / 2;
if(pos <= tm)
update(tl, tm, v*2, pos, val);
else
update(tm+1, tr, v*2+1, pos, val);
t[v] = (t[v*2] * t[v*2+1]) % mod;
}
long long get(int tl, int tr, int v, int l, int r){
if(r < tl || tr < l || r < l)return 1ll;
if(l <= tl && tr <= r){
return t[v];
}
int tm = (tl + tr) / 2;
return (get(tl, tm, v*2, l, r) * get(tm+1, tr, v*2+1, l, r)) % mod;
}
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
void update2(int tl, int tr, int v, int pos, int val){
if(tl == tr){
mxi[v] = val;
return;
}
int tm = (tl + tr) / 2;
if(pos <= tm)
update2(tl, tm, v*2, pos, val);
else
update2(tm+1, tr, v*2+1, pos, val);
mxi[v] = max(mxi[v*2], mxi[v*2+1]);
}
int get2(int tl, int tr, int v, int l, int r){
if(r < tl || tr < l || r < l)return 0;
if(l <= tl && tr <= r){
return mxi[v];
}
int tm = (tl + tr) / 2;
return max(get2(tl, tm, v*2, l, r), get2(tm+1, tr, v*2+1, l, r));
}
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
void upd_cnt(int tl, int tr, int v, int pos, int val){
if(tl == tr){
cnt[v] = val;
return;
}
int tm = (tl + tr) / 2;
if(pos <= tm)
upd_cnt(tl, tm, v*2, pos, val);
else
upd_cnt(tm+1, tr, v*2+1, pos, val);
cnt[v] = cnt[v*2] + cnt[v*2+1];
}
int get_cnt(int tl, int tr, int v, int l, int r){
if(r < tl || tr < l || r < l)return 0;
if(l <= tl && tr <= r){
return cnt[v];
}
int tm = (tl + tr) / 2;
return (get_cnt(tl, tm, v*2, l, r) + get_cnt(tm+1, tr, v*2+1, l, r));
}
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
vector<int>rb(N), vla(N), lb(N, -1);
long long fi(int ind, int val){
long long sum = get(0, n, 1, 0, ind);
long long u = (sum * val) % mod;
return u;
}
int init(int N, int X[], int Y[]){
n = N;
for(int i = 0;i<n;i++){
b[i] = Y[i];
a[i] = X[i];
update(0, n, 1, i, a[i]);
update2(0, n, 1, i, b[i]);
if(a[i] > 1)
upd_cnt(0, n, 1, i, 1);
else
upd_cnt(0, n, 1, i, 0);
}
for(int i = 0;i<n;i++){
if(i == 0){
lb[i] = i;
rb[i] = i;
continue;
}
if(a[i] == 1){
lb[i] = lb[i-1];
rb[i] = i;
rb[lb[i]] = i;
}
if(a[i] > 1){
lb[i] = i;
rb[i] = i;
}
}
for(int i = 0;i<n;i++){
vla[i] = get2(0, n, 1, i, rb[i]);
}
int l = 0, r = n-1, ans = 0;
while(l <= r){
int mid = (l + r) / 2;
if(get_cnt(0, n, 1, mid, n) >= 32){
ans = mid;
l = mid + 1;
}
else r = mid - 1;
}
long long mx = -1, sum = 1, val = -1;
for(int i = ans;i<n;){
int iop = rb[i];
int x = X[i];
int y = vla[i];
if(mx == -1){
mx = i;
sum = 1;
val = y;
}
else{
sum *= x;
if(val / y < sum){
mx = i;
sum = 1;
val = y;
}
}
i = iop + 1;
}
/*cout << "\n";
for(int i = 0;i<n;i++)cout << vla[i] << " ";
cout << "\n";
for(int i = 0;i<n;i++)cout << rb[i] << " ";
cout << "\n\n";
*/
return fi(mx, val);
}
int updateX(int pos, int vl){
update(0, n, 1, pos, vl);
if(a[pos] != vl){
if(vl == 1){
int l2 = 0, r2 = pos-1, ans2 = 0;
while(l2 <= r2){
int mid = (l2 + r2) / 2;
if(get_cnt(0, n, 1, mid, pos-1) == 0){
r2 = mid - 1;
}
else {
ans2 = mid;
l2 = mid + 1;
}
}
int yu = rb[pos];
rb[pos] = pos;
rb[ans2] = yu;
vla[pos] = b[pos];
vla[ans2] = get2(0, n, 1, ans2, rb[ans2]);
}
else if(a[pos] == 1){
int l2 = 0, r2 = pos-1, ans2 = 0;
while(l2 <= r2){
int mid = (l2 + r2) / 2;
if(get_cnt(0, n, 1, mid, pos - 1) == 0){
r2 = mid - 1;
}
else {
ans2 = mid;
l2 = mid + 1;
}
}
rb[pos] = rb[ans2];
if(ans2 != pos)rb[ans2] = pos - 1;
vla[pos] = get2(0, n, 1, pos, rb[pos]);
vla[ans2] = get2(0, n, 1, ans2, rb[ans2]);
}
}
a[pos] = vl;
// cout << "\n";
// for(int i = 0;i<n;i++)cout << vla[i] << " ";
// cout << "\n";
// for(int i = 0;i<n;i++)cout << rb[i] << " ";
// cout << "\n\n";
if(vl == 1)
upd_cnt(0, n, 1, pos, 0);
else
upd_cnt(0, n, 1, pos, 1);
int l = 0, r = n-1, ans = 0;
while(l <= r){
int mid = (l + r) / 2;
if(get_cnt(0, n, 1, mid, n) >= 32){
ans = mid;
l = mid + 1;
}
else r = mid - 1;
}
long long mx = -1, sum = 1, val = -1;
for(int i = ans;i<n;){
int iop = rb[i];
int x = a[i];
int y = vla[i];
if(mx == -1){
mx = i;
sum = 1;
val = y;
}
else{
sum *= x;
if(val / y < sum){
mx = i;
sum = 1;
val = y;
}
}
i = iop + 1;
}
return fi(mx, val);
}
int updateY(int pos, int vl){
b[pos] = vl;
update2(0, n, 1, pos, vl);
int l2 = 0, r2 = pos, ans2 = 0;
while(l2 <= r2){
int mid = (l2 + r2) / 2;
if(get_cnt(0, n, 1, mid, pos) == 0){
r2 = mid - 1;
}
else {
ans2 = mid;
l2 = mid + 1;
}
}
// cout << ans2 << "\n";
vla[ans2] = get2(0, n, 1, ans2, rb[ans2]);
if(ans2 != pos)vla[pos] = vl;
// for(int i = 0;i<n;i++){
// cout << vla[i] << ' ';
// }
// cout << "\n";
int l = 0, r = n-1, ans = 0;
while(l <= r){
int mid = (l + r) / 2;
if(get_cnt(0, n, 1, mid, n) >= 32){
ans = mid;
l = mid + 1;
}
else r = mid - 1;
}
long long mx = -1, sum = 1, val = -1;
for(int i = ans;i<n;){
int iop = rb[i];
int x = a[i];
int y = vla[i];
if(mx == -1){
mx = i;
sum = 1;
val = y;
}
else{
sum *= x;
if(val / y < sum){
mx = i;
sum = 1;
val = y;
}
}
i = iop + 1;
}
return fi(mx, val);
}
/*
7
0 2 1
6 2 1
7 2 1
12 2 1
14 2 1
18 2 1
21 2 1
10
1
2
3
4
5
6
7
8
9
10
*/
/*signed main()
{
// freopen("seq.in", "r", stdin);
// freopen("seq.out", "w", stdout);
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
int tt=1;// cin >> tt;
while(tt--)solve();
}*/
