//#include "grader.cpp"
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
const int N=1e6+5;
const int MOD=1e9+7;
ll a[N],b[N];
int n,s;
struct node{
ld summ;
ll answ;
};
vector<node> ans;
vector<node> v;
node z={0. , 1ll};
node mx(node a,node b){
if(a.summ>b.summ) return a;
else return b;
}
void build(){
s=1;
while(s<n) s*=2;
v.assign(s*2,z);
ans.assign(s*2,z);
for(int i=0;i<s;i++){
v[i+s].answ=a[i];
v[i+s].summ=log2(a[i]);
}
for(int i=1;i<s;i++){
v[i+s].summ+=v[s+i-1].summ;
v[i+s].answ*=v[s+i-1].answ;
v[i+s].answ%=MOD;
}
for(int i=0;i<s;i++){
ans[i+s].answ = (v[i+s].answ*b[i]) % MOD ;
ans[i+s].summ = v[i+s].summ+log2(b[i]);
}
for(int i=s-1;i>0;i--)
ans[i]=mx(ans[i*2+1],ans[i*2]);
}
ll binpow(ll a,ll b){
if(b==0) return 1ll;
if(b==1) return a;
ll ans=binpow(a,b/2)%MOD;
return (b%2==1 ? (ans*a)%MOD:ans);
}
node comb(node a,node b){
return {a.summ+b.summ,(a.answ*b.answ)%MOD};
}
void push(int l,int r,int x){
if(r==l+1) return;
v[x*2]=comb(v[x],v[x*2]);
v[x*2+1]=comb(v[x],v[x*2+1]);
ans[x*2]=comb(ans[x],ans[x*2]);
ans[x*2+1]=comb(ans[x],ans[x*2+1]);
v[x]=z;
ans[x]=mx(ans[x*2],ans[x*2+1]);
}
void updX(int l,int r,int lx,int rx,node val,int x){
if(l>=rx||r<=lx) return;
push(lx,rx,x);
if(lx>=l&&rx<=r){
v[x]=comb(v[x],val);
ans[x]=comb(ans[x],val);
}
int mid=(lx+rx)/2;
updX(l,r,lx,mid,val,x*2);
updX(l,r,mid,rx,val,x*2+1);
ans[x]=mx(ans[x*2],ans[x*2+1]);
}
void updY(int pos,int lx,int rx,node val,int x){
if(rx-lx==1){
ans[x]=val;
return;
}
push(lx,rx,x);
int mid=(lx+rx)/2;
if(mid <= pos) updY(pos,mid,rx,val,x*2);
else updY(pos,lx,mid,val,x*2+1);
ans[x]=mx(ans[x*2], ans[x*2+1]);
}
node pref(int i){
node ans1={0. ,1};
for(i+=s;i>0;i/=2){
ans1.summ+=v[i].summ;
ans1.answ*=v[i].answ;
ans1.answ%=MOD;
}
return ans1;
}
int init(int s, int x[], int y[]) {
n=s;
for(int i=0;i<n;i++){
a[i]=x[i];
b[i]=y[i];
}
build();
int ans1=ans[1].answ;
return ans1;
}
int updateX(int pos, int val) {
a[pos]=val;
int lx=0, rx=s, l=pos, r=s;
node nod={(log2(val)-log2(a[pos])), (val*binpow(a[pos],MOD-2))%MOD};
updX(lx,rx,l,r,nod,1);
return ans[1].answ;
}
int updateY(int pos, int val) {
b[pos]=val;
node x=pref(pos);
node nod={x.summ+log2(val),(x.answ*val)%MOD};
updY(pos,0,s,nod,1);
return ans[1].answ;
}
