#include "horses.h"
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
typedef long long ll;
#define double long double
const int mod=1e9+7, Log=30, maxn=5e5, Log1=19, pot=(1<<Log1);
inline int sum(int a, int b){
if(a+b>=mod){
return a+b-mod;
}
if(a+b<0){
return a+b+mod;
}
return a+b;
}
inline int mul(int a, int b){
return (ll)a*b%mod;
}
inline int pote(int a, int b){
int sol=1;
for(int i=0; i<Log; i++){
if((1<<i)&b){
sol=mul(sol, a);
}
a=mul(a, a);
}
return sol;
}
inline int dij(int a, int b){
return mul(a, pote(b, mod-2));
}
pair < double, int > t[pot*2];
pair < double, int > prop[pot*2];
int a[maxn];
int b[maxn];
void precompute(){
for(int i=1; i<pot*2; i++){
prop[i]={0, 1};
t[i]={0, 1};
}
}
void propagate(int x){
if(prop[x].second==1){
return;
}
t[x].second=mul(t[x].second, prop[x].second);
t[x].first=t[x].first+prop[x].first;
if(x<pot){
prop[x*2]={prop[x*2].first+prop[x].first, mul(prop[x*2].second, prop[x].second)};
prop[x*2+1]={prop[x*2+1].first+prop[x].first, mul(prop[x*2+1].second, prop[x].second)};
}
prop[x]={0, 1};
}
void update(int L, int D, int x, int l, int d, double val1, int val2){
propagate(x);
if(L>=l && D<=d){
t[x]={t[x].first+val1, mul(t[x].second, val2)};
// cout << "upd " << x-pot << ' ' << t[x] << endl;
if(x<pot){
prop[x*2]={prop[x*2].first+val1, mul(prop[x*2].second, val2)};
prop[x*2+1]={prop[x*2+1].first+val1, mul(prop[x*2+1].second, val2)};
}
return;
}
if((L+D)/2>=l){
update(L, (L+D)/2, x*2, l, d, val1, val2);
}
if((L+D)/2+1<=d){
update((L+D)/2+1, D, x*2+1, l, d, val1, val2);
}
propagate(x*2);
propagate(x*2+1);
if(t[x*2].first>t[x*2+1].first){
t[x]=t[x*2];
}
else{
t[x]=t[x*2+1];
}
}
int init(int n, int x[], int y[]){
precompute();
int val=1;
double val1=0;
for(int i=0; i<pot; i++){
if(i<n){
a[i]=x[i];
b[i]=y[i];
val=mul(val, a[i]);
val1+=log(a[i]);
update(0, pot-1, 1, i, i, val1+log(b[i]), mul(val, b[i]));
}
else{
update(0, pot-1, 1, i, i, val1, val);
}
}
return t[1].second;
}
int updateX(int pos, int val){
update(0, pot-1, 1, pos, pot-1, log(val)-log(a[pos]), dij(val, a[pos]));
a[pos]=val;
return t[1].second;
}
int updateY(int pos, int val){
// cout << "val " << b[pos] << ' ' << val << endl;
update(0, pot-1, 1, pos, pos, log(val)-log(b[pos]), dij(val, b[pos]));
b[pos]=val;
return t[1].second;
}
/*
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
int x[n], y[n];
for(int i=0; i<n; i++){
cin >> x[i];
}
for(int i=0; i<n; i++){
cin >> y[i];
}
cout << init(n, x, y) << '\n';
int q;
cin >> q;
int a1, b1, c1;
for(int i=0; i<q; i++){
cin >> a1 >> b1 >> c1;
if(a1==1){
cout << updateX(b1, c1) << '\n';
}
else{
cout << updateY(b1, c1) << '\n';
}
}
return 0;
}
*/
