#include "horses.h"
#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=5e5+5;
const ll inf=1e9;
const ll mod = 1e9 + 7;
set<pii> st;
ll x[mxn],y[mxn];
int n;
ll bigmod(ll a,ll b) {
if(b==0)return 1;
ll mid=b/2;
ll c=bigmod(a,mid);
if(b%2==0)return (c*c)%mod;
c=(c*c)%mod;
return (a*c)%mod;
}
struct segtree {
int tree[4*mxn] = {};
void update(int node,int b,int e,int p,int v) {
if(e<p|| b>p)return;
if(b == e) {
tree[node] = v;
return;
}
int mid=b+e>>1;
int left=node<<1;
int right=left|1;
update(left,b,mid,p,v);
update(right,mid+1,e,p,v);
tree[node]=max(tree[left],tree[right]);
}
int query(int node,int b,int e,int l,int r) {
if(e<l || b>r) return 0;
if(b>=l && e<=r) {
return tree[node];
}
int mid=b+e>>1;
int left=node<<1;
int right=left|1;
return max(query(left,b,mid,l,r),query(right,mid + 1, e, l,r));
}
} seg;
struct BIT
{
ll bit[mxn];
void init() {
for(int i = 1; i < mxn; i++) bit[i] = 1;
}
void update(int p,ll v) {
if(p==0) return;
for(;p<mxn;p+=p&-p) bit[p] = bit[p] * v % mod;
}
ll query(int p) {
ll r = 1;
for(;p>0;p-=p&-p) r = bit[p] * r % mod;
return r;
}
} bt;
int init(int N, int X[], int Y[]) {
bt.init();
n = N;
int last = -1;
for(int i = 0; i < N; i++) {
x[i] = X[i];
y[i] = Y[i];
if(X[i] == 1) {
seg.update(1,1,n,i + 1,Y[i]);
if(last == -1) last = i;
} else {
if(last != -1) {
st.insert({last,i - 1});
last = -1;
}
}
}
if(last != -1) st.insert({last,N - 1});
for(int i = 1; i <= N; i++) {
bt.update(i,X[i - 1]);
}
ll ans = 0;
ll cm = 0;
for(int i = N - 1; i >= 0; i--) {
if(Y[i] > cm) {
ans = bt.query(i + 1) * Y[i] % mod;
cm = Y[i] * X[i];
} else {
cm = cm * X[i];
}
if(cm >= inf) break;
}
return ans;
}
int calc() {
int k = 0;
ll ans = 0;
ll cm = 0;
for(int i = n - 1; i >= 0 && k <= 62; i--,k++) {
ll v1 = bt.query(i + 1);
ll v2 = y[i];
if(x[i] == 1) {
auto it = st.lower_bound({i,i});
if(it == st.end() || it->f > i) it--;
v2 = seg.query(1,1,n,it->f + 1,i + 1);
i = it->f;
}
if(v2 > cm) {
ans = v1 * v2 % mod;
cm = x[i] * v2;
} else {
cm = cm * v2;
}
if(cm >= inf) break;
}
return ans;
}
int updateX(int pos, int val) {
ll tv = bigmod(x[pos],mod - 2);
bt.update(pos + 1, tv);
bt.update(pos + 1,val);
if(x[pos] == 1 && val != 1) {
auto it = st.lower_bound({pos,pos});
if(it == st.end() || it->f > pos) it--;
st.erase(it);
if(it->f != pos) st.insert({it->f,pos - 1});
if(it->s != pos) st.insert({pos + 1,it->s});
seg.update(1,1,n,pos + 1,0);
}
if(val == 1 && x[pos] != 1) {
seg.update(1,1,n,pos + 1,y[pos]);
int l = pos,r = pos;
if(pos > 0 && x[pos - 1] == 1) {
auto it = st.lower_bound({pos - 1,pos - 1});
if(it == st.end() || it->f > pos - 1) it--;
st.erase(it);
l = it->f;
}
if(pos < n - 1 && x[pos + 1] == 1) {
auto it = st.lower_bound({pos + 1,pos + 1});
if(it == st.end() || it->f > pos + 1) it--;
st.erase(it);
r = it->s;
}
st.insert({l,r});
}
x[pos] = val;
return calc();
}
int updateY(int pos, int val) {
y[pos] = val;
if(x[pos] == 1) seg.update(1,1,n,pos + 1,val);
return calc();
}
