#include "horses.h"
#include <bits/stdc++.h>
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define x first
#define y second
#define debug(...) "["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int>pii;
const int maxn=5e5+100;
const int mod=1e9+7;
const ld eps=1e-6;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll pwr(ll a, ll pw)
{
ll ret=1;
while(pw>0)
{
if(pw&1)ret=ret*a%mod;
a=a*a%mod;
pw>>=1;
}
return ret;
}
ll modinv(ll a)
{
return pwr(a, mod-2);
}
int N;
ll X[maxn], Y[maxn];
ld seg[maxn*4], Xpref[maxn], lazy[maxn*4];
void build(int id=1, int l=0, int r=N-1)
{
if(l == r)
{
seg[id]=Xpref[l]+log2((ld)Y[l]);
return;
}
int mid=(l+r)/2;
build(id*2, l, mid);
build(id*2+1, mid+1, r);
seg[id]=max(seg[id*2], seg[id*2+1]);
}
void laz(int id, ld d)
{
seg[id]+=d;
lazy[id]+=d;
}
void shift(int id)
{
if(lazy[id])
{
laz(id*2, lazy[id]);
laz(id*2+1, lazy[id]);
lazy[id]=0;
}
}
void modify(int x, int y, ld d, int id=1, int l=0, int r=N-1)
{
if(l > y || r < x)return;
if(l >= x && r <= y)
{
laz(id, d);
return;
}
shift(id);
int mid=(l+r)/2;
modify(x, y, d, id*2, l, mid);
modify(x, y, d, id*2+1, mid+1, r);
seg[id]=max(seg[id*2], seg[id*2+1]);
}
ld query(int x, int y, int id=1, int l=0, int r=N-1)
{
if(l > y || r < x)return 0;
if(l >= x && r <= y)return seg[id];
shift(id);
int mid=(l+r)/2;
return max(query(x, y, id*2, l, mid), query(x, y, id*2+1, mid+1, r));
}
ll F[maxn];
void upd(int p, ll val)
{
for(; p<=N; p+=p&-p)
F[p]=(F[p]*val)%mod;
}
ll get(int p)
{
ll ret=1;
for(; p>0; p-=p&-p)
ret=(ret*F[p])%mod;
return ret;
}
int getans()
{
int l=0, r=N-1;
ld mx=query(0, N-1);
while(l < r)
{
int mid=(l+r)/2;
if(query(l, mid) > mx)r=mid;
else l=mid+1;
}
//cout<<debug(l)<<"\n";
return (int)((get(l+1)*Y[l])%mod);
}
int init(int n, int x[], int y[])
{
N=n;
for(int i=0; i<N; i++)
X[i]=x[i], Y[i]=y[i];
for(int i=0; i<N; i++)
{
ld v=X[i];
F[i+1]=1;
Xpref[i]=log2(v);
if(i > 0)Xpref[i]+=Xpref[i-1];
}
for(int i=1; i<=N; i++)
upd(i, X[i-1]);
build();
return getans();
}
int updateX(int p, int val)
{
ld d=log2((ld)val)-log2((ld)X[p]);
ll up=modinv(X[p])*(ll)val%mod;
X[p]=val;
modify(0, p, d);
upd(p+1, up);
return getans();
}
int updateY(int p, int val)
{
ld d=log2((ld)val)-log2((ld)Y[p]);
Y[p]=val;
modify(p, p, d);
return getans();
}
/*int main()
{
ios_base::sync_with_stdio(false), cin.tie(0);
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int n, A[maxn], B[maxn];
cin>>n;
for(int i=0; i<n; i++)
cin>>A[i];
for(int i=0; i<n; i++)
cin>>B[i];
cout<<init(n, A, B)<<"\n";
int m;
cin>>m;
while(m--)
{
int a, b, c;
cin>>a>>b>>c;
if(a == 1)cout<<updateX(b, c)<<"\n";
else cout<<updateY(b, c)<<"\n";
}
return 0;
}*/
