#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e9+7;
ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ll,ii>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<ll> distr;
ll rnd(ll a, ll b){return distr(rng)%(b-a+1)+a;}
#include "horses.h"
/*
int init(int N, int X[], int Y[]);
int updateX(int pos, int val);
int updateY(int pos, int val);
int main() {
int N;
cin>>N;
int *X = (int*)malloc(sizeof(int)*(unsigned int)N);
int *Y = (int*)malloc(sizeof(int)*(unsigned int)N);
for (int i = 0; i < N; i++) {
cin>>X[i];
}
for (int i = 0; i < N; i++) {
cin>>Y[i];
}
printf("%d\n",init(N,X,Y));
int M;
cin>>M;
for (int i = 0; i < M; i++) {
int type;
cin>>type;
int pos;
int val;
cin>>pos>>val;
if (type == 1) {
printf("%d\n",updateX(pos,val));
} else if (type == 2) {
printf("%d\n",updateY(pos,val));
}
}
return 0;
}
*/
ll seg[2000005]={0},se[2000005]={0};
ll y[500000];
ll n;
void build(ll s,ll e,ll idx){
if(s == e){
seg[idx] = y[s-1];
return;
}
ll mid = (s+e)/2;
build(s,mid,idx*2);
build(mid+1,e,idx*2+1);
seg[idx] = max(seg[idx*2],seg[idx*2+1]);
}
void update(ll s,ll e,ll qs,ll qe,ll idx,ll k){
if(s == e && s == qs){
seg[idx] = k;
return;
}
if(qs > e || qe < s){
return;
}
ll mid = (s+e)/2;
update(s,mid,qs,qe,idx*2,k);
update(mid+1,e,qs,qe,idx*2+1,k);
seg[idx] = max(seg[idx*2],seg[idx*2+1]);
}
ll query(ll s,ll e,ll qs,ll qe,ll idx){
if(qs <= s && e <= qe){
return seg[idx];
}
if(qs > e || qe < s){
return 0;
}
ll mid = (s+e)/2;
ll a = query(s,mid,qs,qe,idx*2);
ll b = query(mid+1,e,qs,qe,idx*2+1);
return max(a,b);
}
ll x[500000];
void build2(ll s,ll e,ll idx){
if(s == e){
se[idx] = x[s-1];
return;
}
ll mid = (s+e)/2;
build2(s,mid,idx*2);
build2(mid+1,e,idx*2+1);
se[idx] = (se[idx*2] * se[idx*2+1]) % INF;
}
void update2(ll s,ll e,ll qs,ll qe,ll idx,ll k){
if(s == e && s == qs){
se[idx] = k;
return;
}
if(qs > e || qe < s){
return;
}
ll mid = (s+e)/2;
update2(s,mid,qs,qe,idx*2,k);
update2(mid+1,e,qs,qe,idx*2+1,k);
se[idx] = (se[idx*2] * se[idx*2+1]) % INF;
}
ll query2(ll s,ll e,ll qs,ll qe,ll idx){
if(qs <= s && e <= qe){
return se[idx];
}
if(qs > e || qe < s){
return 1;
}
ll mid = (s+e)/2;
ll a = query2(s,mid,qs,qe,idx*2);
ll b = query2(mid+1,e,qs,qe,idx*2+1);
return (a * b) % INF;
}
set<ii>ar;
ll power(ll a,ll b){
if(b == 0){
return 1;
}
if(b == 1){
return a;
}
ll ans = power(a,b/2);
ans *= ans;
ans %= INF;
if(b % 2){
ans *= a;
}
return ans % INF;
}
ll inv(ll a){
return power(a,INF-2);
}
int solve(void){
ll num = 1;
ll p = 0;
ll product = query2(1,n,1,n,1);
ll num2 = 1,y2 = y[n-1];
auto it = ar.begin();
ll last = n;
while(num <= 1e9 && p != ar.size()){
ll y1 = query(1,n,-(*it).F+2,last,1);
if(y1 * num2 > y2 * num){
y2 = y1;
num2 = num;
}
last = -(*it).F+1;
num *= (*it).S;
it++;
p++;
}
if(num <= 1e9){
ll y1 = query(1,n,1,last,1);
if(y1 * num2 > y2 * num){
y2 = y1;
num2 = num;
}
}
ll ans = (((product * inv(num2)) % INF) * y2) % INF;
return ans;
}
int init(int N, int X[], int Y[]) {
n = N;
f(i,0,N){
y[i] = Y[i];
x[i] = X[i];
}
build(1,N,1);
build2(1,N,1);
ll ans = 0;
ll pos = N - 1;
while(pos >= 0){
if(x[pos] > 1){
ar.insert(ii(-pos,x[pos]));
}
pos--;
}
return solve();
}
int updateX(int pos, int val){
if(ar.count(ii(-pos,x[pos]))){
ar.erase(ii(-pos,x[pos]));
}
x[pos] = val;
update2(1,n,pos+1,pos+1,1,val);
if(val != 1){
ar.insert(ii(-pos,x[pos]));
}
return solve();
}
int updateY(int pos, int val){
y[pos] = val;
update(1,n,pos+1,pos+1,1,val);
return solve();
}
/*
3
2 1 3
3 4 1
1
2 1 2
*/
