#include "horses.h"
#ifdef DEBUG
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
#define cmin(a, b) a=min(a, b)
#define cmax(a, b) a=max(a, b)
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define int long long
const int MOD=1e9+7;
int fastpow(int x, int y) {
if (y==1) return x;
if (y%2) return (fastpow(x, y-1)*x)%MOD;
int res=fastpow(x, y/2);
return (res*res)%MOD;
}
int inv(int x) { return fastpow(x, MOD-2); }
struct segtree {
int n;
vector<int> t;
segtree() {}
void build(int _n, vector<int> &x) {
n=_n;
t.resize(2*n);
for (int i=0; i<n; i++) t[i+n]=x[i];
for (int i=n-1; i>0; i--) t[i]=(t[i<<1]*t[i<<1|1])%MOD;
}
void update(int pos, int x) {
for (t[pos+=n]=x; pos>1; pos>>=1) t[pos>>1]=(t[pos]*t[pos^1])%MOD;
}
int query(int l, int r) {
r++;
int ans=1;
for (l+=n, r+=n; l<r; l>>=1, r>>=1) {
if (l&1) ans=(ans*t[l++])%MOD;
if (r&1) ans=(ans*t[--r])%MOD;
}
return ans;
}
};
struct segtreeY {
int n;
vector<int> t;
segtreeY() {}
void build(int _n, vector<int> &x) {
n=_n;
t.resize(2*n);
for (int i=0; i<n; i++) t[i+n]=x[i];
for (int i=n-1; i>0; i--) t[i]=max(t[i<<1], t[i<<1|1]);
}
void update(int pos, int x) {
for (t[pos+=n]=x; pos>1; pos>>=1) t[pos>>1]=max(t[pos], t[pos^1]);
}
int query(int l, int r) {
r++;
int ans=1;
for (l+=n, r+=n; l<r; l>>=1, r>>=1) {
if (l&1) cmax(ans, t[l++]);
if (r&1) cmax(ans, t[--r]);
}
return ans;
}
};
int n;
vector<int> x, y;
set<int> beg;
segtree st;
segtreeY st2;
int calc() {
int mul=0, best=-1, val=0;
for (int i=n-1; i>=0; i--) {
if (mul>1e9) break;
if (x[i]==1) {
auto j=*prev(beg.upper_bound(i)), quer=st2.query(j, i);
assert(j<=i);
if (mul<quer) mul=quer, best=i, val=quer;
i=j;
continue;
}
if (mul<y[i]) mul=y[i], best=i, val=y[i];
mul*=x[i];
}
int ans=(st.query(0, best)*val)%MOD;
return ans;
}
signed init(signed N, signed X[], signed Y[]) {
n=N;
for (int i=0; i<n; i++) {
x.pb(X[i]), y.pb(Y[i]);
if (x[i]==1 && (i==0 || x[i-1]!=1)) beg.insert(i);
}
st.build(n, x);
st2.build(n, y);
return calc();
}
signed updateX(signed pos, signed val) {
if (x[pos]==val) return calc();
if (pos+1<n && x[pos+1]==1) {
if (val!=1) beg.insert(pos+1);
else beg.erase(pos+1);
}
if (beg.count(pos)) beg.erase(pos);
if (val==1 && (pos==0 || x[pos-1]!=1)) beg.insert(pos);
x[pos]=val;
st.update(pos, val);
return calc();
}
signed updateY(signed pos, signed val) {
y[pos]=val;
st2.update(pos, val);
return calc();
}
