# include "horses.h"
//# pragma GCC optimize("Ofast,no-stack-protector")
//# pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
# pragma GCC optimize("Ofast")
# pragma GCC optimization ("unroll-loops")
# include "bits/stdc++.h"
/*
# include <ext/pb_ds/tree_policy.hpp>
# include <ext/pb_ds/assoc_container.hpp>
# include <ext/rope>
*/
std::pair<int,int> DR[] = {{-1,0},{0,1},{1,0},{0,-1},{-1,1},{-1,-1},{1,1},{1,-1}};
# define ll long long
# define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
# define rc(s) return cout << s,0
# define rcg(s) cout << s;exit(0)
# define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
# define db(x) cerr << #x << " = " << x << '\n'
# define pb push_back
# define mp make_pair
# define all(s) s.begin(),s.end()
# define sz(x) (int)((x).size())
# define int ll
using namespace std;
const int mod = 1e9 + 7;
set<int>s,S;
int fen[1 << 19],x[1 << 19],y[1 << 19],t[1 << 21],n,b[1 << 19];
void upd(int nod,int l,int r,int pos,int val)
{
if(l == r)
{
t[nod] = val;
return ;
}
int mid = l + r >> 1;
if(pos <= mid) upd(nod << 1,l,mid,pos,val);
else upd(nod << 1 | 1,mid + 1,r,pos,val);
t[nod] = max(t[nod << 1],t[nod << 1 | 1]);
}
int qry(int nod,int tl,int tr,int l,int r)
{
if(l > r) return 0;
if(tl == l && tr == r) return t[nod];
int mid = tl + tr >> 1;
return max(qry(nod << 1,tl,mid,l,min(mid,r)),qry(nod << 1 | 1,mid + 1,tr,max(mid + 1,l),r));
}
void UPD(int pos,int val)
{
pos++;
for(int i = pos;i <= n;i += (i & (-i)))
{
fen[i] *= val;
fen[i] %= mod;
}
}
int QRY(int pos)
{
pos++;
int ans = 1;
for(int i = pos;i;i -= (i & (-i)))
{
ans *= fen[i];
ans %= mod;
}
return ans;
}
int f()
{
auto it = --(S.end());
for(int i = 0;i <= 35;i++)
{
if(it != S.begin()) it--;
}
int pos = (*it) + 1;
vector<pair<int,int>>vec;
vector<int>hm;
int i = pos;
while(i < n)
{
if(x[i] == 1)
{
int r = *(S.upper_bound(i)) - 1;
vec.pb(mp(x[i],qry(1,0,n - 1,i,r)));
hm.pb(i);
i = r + 1;
}
else
{
vec.pb(mp(x[i],y[i]));
hm.pb(i);
i++;
}
}
for(int i = 0;i < sz(vec);i++) b[i] = 1;
for(int i = 0;i < sz(vec);i++)
{
int j = i + 1;
int prod = 1;
while(j < sz(vec))
{
prod *= vec[j].first;
if(prod >= vec[i].second)
{
b[i] = 0;
break;
}
else if(prod * vec[j].second >= vec[i].second)
{
b[i] = 0;
}
else b[j] = 0;
j++;
}
}
int f = 0;
for(int i = 0;i < sz(vec);i++)
{
if(b[i]) f = i;
}
return ((vec[f].second * QRY(hm[f])) % mod);
}
# undef int
int init(int N, int X[], int Y[])
{
# define int ll
n = N;
S.insert(n);S.insert(-1);
for(int i = 1;i <= n;i++) fen[i] = 1;
for(int i = 0;i < n;i++)
{
x[i] = X[i];
y[i] = Y[i];
UPD(i,x[i]);
if(X[i] > 1) S.insert(i);
upd(1,0,n - 1,i,Y[i]);
}
//cout << f() << '\n';
return f();
}
int pw(int val,int p)
{
int ans = 1;
for(int i = 0;(1LL << i) <= p;i++)
{
if(p & (1LL << i))
{
ans *= val;
ans %= mod;
}
val *= val;
val %= mod;
}
return ans;
}
# undef int
int updateX(int pos, int val)
{
# define int ll
if(x[pos] > 1) S.erase(S.find(pos));
if(val > 1) S.insert(pos);
UPD(pos,(val * pw(x[pos],mod - 2)) % mod);
x[pos] = val;
//cout << f() << '\n';
return f();
}
# undef int
int updateY(int pos, int val)
{
# define int ll
upd(1,0,n - 1,pos,val);
y[pos] = val;
//cout << f() << '\n';
return f();
}
