#include <bits/stdc++.h>
#include "horses.h"
#define ll long long
#define lp(i,a,b) for(int i=a;i<b;i++)
#define pii pair<int,int>
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
const int MOD = 1e9+7 ;
const int maxn=5e5+10;
using namespace std ;
int n ;
struct segOfSum
{
double v[maxn*4] ;
void pointUpd(int pos, int l, int r,int x , double val)
{
if(l==r) { v[pos] = val ; return ; }
int mid = (l+r)/2 ;
if(x<=mid) pointUpd(pos*2,l,mid,x,val) ;
else pointUpd(pos*2+1,mid+1,r,x,val) ;
v[pos] = v[pos*2] + v[pos*2+1] ;
}
double query(int pos, int l, int r, int beg, int en)
{
if(l>en || r < beg) return 0 ;
if(l>=beg && r<=en) return v[pos] ;
int mid=(l+r)/2 ;
double rl = query(pos*2,l,mid,beg,en) ;
double rr = query(pos*2+1,mid+1,r,beg,en) ;
return rl+rr ;
}
} ;
//------- x -------
int bit[maxn] ;
void add(int x, int val)
{ for(int i=x;i<maxn;i+=(i&-i)) bit[i]+=val ; }
int queryb(int x)
{
int tot = 0 ;
for(int i = x ; i>0 ; i-=(i&-i)) tot += bit[i] ;
return tot ;
}
//------- x -------
double tree[maxn*4] ;
int best[maxn*4] ;
segOfSum mySeg ;
int m(int l, int r){return (l+r)/2 ;}
void merge(int pos)
{
int index1 = best[pos*2] ;
int index2 = best[pos*2+1] ;
int q = queryb(index2) - queryb(index1) ;
tree[pos] = tree[pos*2+1] ;
best[pos] = best[pos*2+1] ;
double x = mySeg.query(1,0,n,index1+1,index2) ;
if( q<30 && (x + tree[pos*2+1] < tree[pos*2]) )
tree[pos] = tree[pos*2] , best[pos] = best[pos*2];
}
void pointUpd(int pos, int l, int r, int x, double v)
{
if(l==r)
{
tree[pos] = v ;
best[pos] = x ;
return ;
}
if(x<=m(l,r)) pointUpd(pos*2,l,m(l,r),x,v) ;
else pointUpd(pos*2+1, m(l,r)+1,r,x,v) ;
merge(pos) ;
}
void print(int pos, int l, int r)
{
printf("%d %d -> %d , %f\n" , l , r , best[pos] , pow(2,tree[pos])) ;
if(l==r) return ;
print(pos*2,l,m(l,r)) ;
print(pos*2+1, m(l,r)+1,r ) ;
}
//------- x -------
int x[maxn] , y[maxn] ;
ll expo(ll x, int n)
{
if(n==0) return 1 ;
if(n==1) return x ;
if(n%2==0)
{
ll aux = expo(x, n/2) ;
return (aux*aux)%MOD ;
}
ll aux = expo(x,n-1) ;
return (aux*x)%MOD ;
}
ll ans()
{
double k = mySeg.query(1,0,n,0, best[1] ) ;
k += log2(y[ best[1] ] ) ;
int myInt = int(k) ;
while(myInt < k) myInt ++ ;
double now = expo(2,--myInt) * pow(2,k-myInt);
ll myAns = int(now) ;
while(myAns<now) myAns ++ ;
return myAns%MOD ;
} ;
int updateY(int pos, int val)
{
pos++ ;
pointUpd(1,0,n,pos,log2(val)) ;
y[pos] = val ;
return ans() ;
}
int updateX(int pos, int val)
{
pos++ ;
mySeg.pointUpd(1,0,n,pos,log2(val)) ;
if(x[pos] > 1) add(pos,-1) ;
if(val > 1) add(pos,1) ;
pointUpd(1,0,n,pos,log2(y[pos])) ;
x[pos] = val ;
return ans() ;
}
int init(int N, int X[] , int Y[])
{
//Crapy initializations
n = N ;
for(int i = n ; i > 0 ; i--) x[i] = X[i-1] , y[i] = Y[i-1] ;
lp(i,1,n+1)
mySeg.pointUpd(1,0,n,i,log2(x[i])) ;
lp(i,1,n+1)
if(x[i]>1) add(i,1) ;
lp(i,1,n+1)
pointUpd(1,0,n,i,log2(y[i])) ;
return ans() ;
}
