#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;
ll x[mxn],y[mxn];
int n;
set<int> st;
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 calc() {
if(st.empty()) {
return seg.query(1,1,n,1,n);
}
int k = 0;
ll ans = 0;
ll cm = 0;
int last = n;
for(auto it = st.rbegin(); it != st.rend() && k <= 62; it++,k++) {
int i = *it;
if(last - i > 1) {
ll v1 = bt.query(i + 2);
ll v2 = seg.query(1,1,n, i + 2, last);
if(v2 > cm) {
ans = v1 * v2 % mod;
cm = v2;
}
}
last = i;
ll v1 = bt.query(i + 1);
ll v2 = y[i];
if(v2 > cm) {
ans = v1 * v2 % mod;
cm = x[i] * v2;
} else {
cm = cm * x[i];
}
if(cm >= inf) break;
}
return ans;
}
int init(int N, int X[], int Y[]) {
for(int i = 0; i < N; i++) {
x[i] = X[i];
y[i] = Y[i];
if(X[i] != 1) st.insert(i);
else {
seg.update(1,1,N,i + 1,y[i]);
}
}
bt.init();
n = N;
for(int i = 1; i <= N; i++) {
bt.update(i,X[i - 1]);
}
return calc();
}
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) {
st.erase(pos);
seg.update(1,1,n,pos + 1,0);
}
if(val == 1) {
st.insert(pos);
seg.update(1,1,n,pos + 1,y[pos]);
}
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();
}
