#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const ll dim=1<<19;
ll left(ll p){return 2*p+1;}
ll right(ll p){return left(p)+1;}
ll parent(ll p){return (p-1)/2;}
ll N,Q;
vector<ll> sol((1<<20)-1);//indice massimo
vector<ll> costo(1<<19);
vector<pair<ll,bool> > horses((1<<20)-1,{1,0});
pair<ll,bool> prodotto(ll pos,ll da,ll a,ll ini,ll fin){
if(a<ini || da>fin)return {1,0};
if(da>=ini && a<=fin)return horses[pos];
pair<ll,bool> k=prodotto(left(pos),da,(a+da)/2,ini,fin);
pair<ll,bool> k1=prodotto(right(pos),(a+da)/2+1,a,ini,fin);
pair<ll,bool> g={0,0};
if(k.second || k1.second || k.first*k1.first>=mod)g.second=1;
g.first=(k.first*k1.first)%mod;
return g;
}
pair<ll,ll> crea_albero(ll pos,ll a,ll b){
if(a==b)return horses[pos];
pair<ll,ll> k=crea_albero(left(pos),a,(a+b)/2);
pair<ll,ll> k1=crea_albero(right(pos),(a+b)/2+1,b);
if(k.second|| k1.second || k.first*k.second>mod)horses[pos].second=1;
horses[pos].first=(k.first*k1.first)%mod;
return horses[pos];
}
void update_cavalli(ll pos,ll val){
horses[pos].first=val;
for(ll i=parent(pos);i>=0;i=parent(i)){
if(horses[left(i)].second || horses[right(i)].second || horses[left(i)].first*horses[right(i)].first>mod)horses[i].second=1;
horses[i].first=(horses[left(i)].first*horses[right(i)].first)%mod;
if(i==0)break;
}
}
ll crea_albero_sol(ll pos,ll a,ll b){
if(a==b)return sol[pos]=a;
ll k=crea_albero_sol(left(pos),a,(a+b)/2);
ll k1=crea_albero_sol(right(pos),(a+b)/2+1,b);
pair<ll,bool> prod=prodotto(0,0,dim-1,k+1,k1);
if(prod.second==1 || prod.first*costo[k1]>costo[k])return sol[pos]=k1;
return sol[pos]=k;
}
int init(int N,int* X,int* Y){
for(ll i=0;i<N;i++){
horses[i+dim-1].first=(ll)(X[i]);
}
crea_albero(0,0,dim-1);
for(ll i=0;i<N;i++){
costo[i]=Y[i];
}
crea_albero_sol(0,0,dim-1);
ll best=sol[0];
return (int)((costo[best]*prodotto(0,0,dim-1,0,best).first)%mod);
}
void update_sol(ll pos){
for(ll i=parent(pos);i>=0;i=parent(i)){
ll k=sol[left(i)];
ll k1=sol[right(i)];
pair<ll,bool> prod=prodotto(0,0,dim-1,k+1,k1);
if(prod.second==1 || prod.first*costo[k1]>costo[k])sol[i]=k1;
else sol[i]=k;
if(i==0)break;
}
}
int updateX(int pos,int val){
update_cavalli(pos+dim-1,val);
update_sol(pos+dim-1);
ll best=sol[0];
return (int)((costo[best]*prodotto(0,0,dim-1,0,best).first)%mod);
}
int updateY(int pos,int val){
costo[pos]=(ll)(val);
update_sol(pos+dim-1);
ll best=sol[0];
return (int)((costo[best]*prodotto(0,0,dim-1,0,best).first)%mod);
}/*
ll main(){
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
//ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll N;
cin>>N;
ll x[N],y[N];
for(ll i=0;i<N;i++)cin>>x[i];
for(ll i=0;i<N;i++)cin>>y[i];
cout<<init(N,x,y)<<endl;
ll Q;
cin>>Q;
for(ll i=0;i<Q;i++){
ll a,b,c;
cin>>a>>b>>c;
if(a==1)cout<<updateX(b,c)<<endl;
else cout<<updateY(b,c)<<endl;
}
return 0;
}*/
