#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5+23;
const int mod = 1000000007;
int n;
ll x[N],y[N];
ll dp[105][1005];
ll dajdp(){
for(int i = 0; i <= n; i++){
for(int j = 0; j <= 1000; j++){
dp[i][j] = -1;
}
}
dp[0][1] = 0;
for(int i = 1; i <= n; i++){ /// nakon kraja i-te godine
for(ll j = 0; j <= 1000; j++){ /// imam j konja posle prodavanja
int nagore = (j+x[i]-1)/x[i];
nagore *= x[i];
for(ll pre = nagore; pre <= 1000; pre += x[i]){ /// koliko sam konja imao pre prodavanja
if(dp[i-1][pre/x[i]] != -1) dp[i][j] = max(dp[i][j],dp[i-1][pre/x[i]]+(pre-j)*y[i]);
}
}
}
return dp[n][0];
}
bool cmp(int i,int j){
if(i == j) return 0;
if(i < j){
ll prod = y[j];
for(int h = i+1; h <= j; h++){ /// da li nekad prestigne ili postane jednako y[i]?
if(x[h] >= (y[i]+prod-1)/prod) return 0;
else prod *= x[h];
}
return 1;
}
else{
ll prod = y[i];
for(int h = j+1; h <= i; h++){
if(x[h] >= (y[j]+prod-1)/prod) return 1;
else prod *= x[h];
}
return 0;
}
}
ll probaj(){
vector <int> v;
for(int i = 1; i <= n; i++) v.push_back(i);
sort(v.begin(),v.end(),cmp);
int pos = v[0];
ll sol = 1;
for(int i = 1; i <= pos; i++){
sol *= x[i];
sol %= mod;
}
sol *= y[pos];
sol %= mod;
return sol;
}
vector <ll> novx,novy;
bool cmp1(pair <int,int> a,pair <int,int> b){
int i = a.first,j = b.first;
if(i == j) return 0;
if(i < j){
ll prod = novy[j];
for(int h = i+1; h <= j; h++){ /// da li nekad prestigne ili postane jednako y[i]?
if(novx[h] >= (novy[i]+prod-1)/prod) return 0;
else prod *= novx[h];
}
return 1;
}
else{
ll prod = novy[i];
for(int h = j+1; h <= i; h++){
if(novx[h] >= (novy[j]+prod-1)/prod) return 1;
else prod *= novx[h];
}
return 0;
}
}
int drvox[4*N],drvoy[4*N];
void build(int i,int j,int node){
if(i == j){
drvox[node] = (x[i] != 1);
drvoy[node] = y[i];
return;
}
int mid = i+(j-i)/2;
build(i,mid,2*node);
build(mid+1,j,2*node+1);
drvox[node] = drvox[2*node]+drvox[2*node+1];
drvoy[node] = max(drvoy[2*node],drvoy[2*node+1]);
}
void updatex(int i,int j,int pos,int val,int node){
if(i == j){
drvox[node] = (val != 1);
return;
}
int mid = i+(j-i)/2;
if(pos <= mid){
updatex(i,mid,pos,val,2*node);
}
else{
updatex(mid+1,j,pos,val,2*node+1);
}
drvox[node] = drvox[2*node]+drvox[2*node+1];
}
void updatey(int i,int j,int pos,int val,int node){
if(i == j){
drvoy[node] = val;
return;
}
int mid = i+(j-i)/2;
if(pos <= mid){
updatey(i,mid,pos,val,2*node);
}
else{
updatey(mid+1,j,pos,val,2*node+1);
}
drvoy[node] = max(drvoy[2*node],drvoy[2*node+1]);
}
int getx(int i,int j,int l,int r,int node){
if(j < l || i > r) return 0;
if(l <= i && r >= j) return drvox[node];
int mid = i+(j-i)/2;
return getx(i,mid,l,r,2*node)+getx(mid+1,j,l,r,2*node+1);
}
int gety(int i,int j,int l,int r,int node){
if(j < l || i > r) return 0;
if(l <= i && r >= j) return drvoy[node];
int mid = i+(j-i)/2;
return max(gety(i,mid,l,r,2*node),gety(mid+1,j,l,r,2*node+1));
}
ll bit[N];
void update(int pos,ll val){
while(pos <= n){
bit[pos] *= val;
bit[pos] %= mod;
pos += (pos & (-pos));
}
}
ll daj(int pos){
ll ret = 1;
while(pos){
ret *= bit[pos];
ret %= mod;
pos -= (pos & (-pos));
}
return ret;
}
ll probaj1(){
novx = novy = {0};
vector <pair<int,int>> v;
int pos = n,br = 1;
for(int pr = min(30,drvox[1]); pr >= 1; pr--){ /// nadji tacno poziciju pr-tog nejedan elementa od nazad
int l = 1,r = n,nd = 1;
int cuvaj = 0;
while(l != r){
int mid = l+(r-l)/2;
if(cuvaj+drvox[2*nd+1] >= pr){ /// idem desno
l = mid+1;
nd = 2*nd+1;
}
else{ /// idem levo
cuvaj += drvox[2*nd+1];
r = mid;
nd = 2*nd;
}
}
//cout << "za " << pr << " je " << l << endl;
if(pr == drvox[1] && l != 1){ /// tacno poslednji od nazad, onda uracunaj i keceve pre njega
v.push_back({br,1});
novx.push_back(1);
/*ll sta = gety(1,n,1,l-1,1);
novy.push_back(sta);*/
br++;
}
v.push_back({br,l});
novx.push_back(x[l]); /// y ces posle
br++;
}
/*cout << "dobijam " << v.size() << endl;
for(auto f : v){
cout << f.first << " " << f.second << endl;
}
cout << novx.size() << endl;
for(auto f : novx){
cout << f << " ";
}
cout << endl;*/
for(int i = 1; i < v.size(); i++){
int levo = v[i-1].second,desno = v[i].second-1;
ll sta = gety(1,n,levo,desno,1);
novy.push_back(sta);
}
ll sta = gety(1,n,v.back().second,n,1);
novy.push_back(sta);
/*cout << novy.size() << endl;
for(auto f : novy){
cout << f << " ";
}
cout << endl;*/
/*for(int puta = 1; puta <= 30; puta++){
if(pos <= 0) break;
int l = 1,r = pos,ans = 0;
while(l <= r){
int mid = l+(r-l)/2;
if(getx(1,n,mid,pos,1) == 1){
ans = mid;
r = mid-1;
}
else{
l = mid+1;
}
}
if(ans == 0){
v.push_back({br,pos});
novx.push_back(x[pos]);
novy.push_back(y[pos]);
br++;
pos--;
continue;
}
ll sta = gety(1,n,ans,pos,1);
if(ans == 1){
v.push_back({br,ans});
novx.push_back(x[ans]);
novy.push_back(sta);
pos = ans-1;
br++;
continue;
}
v.push_back({br,ans-1});
novx.push_back(x[ans-1]);
novy.push_back(max(y[ans-1],sta));
pos = ans-2;
br++;
}*/
/*cout << "na kraju " << endl;
cout << v.size() << endl;
for(auto f : v){
cout << f.first << " " << f.second << endl;
}
cout << endl;
cout << novx.size() << endl;
for(auto f : novx){
cout << f << " ";
}
cout << endl;
cout << novy.size() << endl;
for(auto f : novy){
cout << f << " ";
}
cout << endl;*/
sort(v.begin(),v.end(),cmp1);
/*cout << "posle sortiranja " << v.size() << endl;
for(auto f : v){
cout << f.first << " " << f.second << endl;
}*/
/*cout << "posle sortiranja" << endl;
cout << v.size() << endl;
for(auto f : v){
cout << f.first << " " << f.second << endl;
}
cout << endl;*/
int poz = v[0].second;
//cout << "poz je " << poz << endl;
ll sol = daj(poz);
//cout << "sol je " << sol << endl;
ll sacim = novy[v[0].first];
sol *= sacim;
sol %= mod;
return sol;
}
ll init(int n1,int *x1,int *y1){
n = n1;
for(int i = 1; i <= n; i++) x[i] = x1[i-1], y[i] = y1[i-1];
/*ll pr = 1,prvi = 1;
for(int i = 1; i <= n; i++){
if(x[i] > 1000/pr) prvi = 0;
else pr *= x[i];
}
if(n <= 10 && prvi){
return dajdp();
}*/
build(1,n,1);
for(int i = 1; i <= n; i++){
bit[i] = 1;
}
for(int i = 1; i <= n; i++){
update(i,x[i]);
}
return probaj1();
}
ll fp(ll x,ll y){
if(y == 0) return 1;
ll p = fp(x,y/2);
p = (p*p)%mod;
if(y&1) p = (p*x)%mod;
return p;
}
ll updateX(int pos,int val){
pos++;
updatex(1,n,pos,val,1);
ll v = fp(x[pos],mod-2);
update(pos,v);
v = val;
update(pos,v);
x[pos] = val;
return probaj1();
}
ll updateY(int pos,int val){
pos++;
updatey(1,n,pos,val,1);
y[pos] = val;
return probaj1();
}
/*int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int a;
cin >> a;
int *prvi = (int*)malloc(sizeof(int)*a);
int *drugi = (int*)malloc(sizeof(int)*a);
for(int i = 1; i <= a; i++){
int x;
cin >> x;
prvi[i-1] = x;
}
for(int i = 1; i <= a; i++){
int x;
cin >> x;
drugi[i-1] = x;
}
cout << init(a,prvi,drugi) << endl;
cout << updateY(1,2) << endl;
}*/
