Inspired by the tv series Stranger Things, bear Limak is going for a walk between two mirror worlds.

There are two perfect binary trees of height H, each with the standard numeration of vertices from 1 to 2^H-1. The root is 1 and the children of x are 2 \cdot x and 2 \cdot x + 1.

Let L denote the number of leaves in a single tree, L = 2^{H-1}.

You are given a permutation P_1, P_2, \ldots, P_L of numbers 1 through L. It describes L special edges that connect leaves of the two trees. There is a special edge between vertex L+i-1 in the first tree and vertex L+P_i-1 in the second tree.

graph for sample1

drawing for the first sample test, permutation P = (2, 3, 1, 4), special edges in green

Let's define product of a cycle as the product of numbers in its vertices. Compute the sum of products of all simple cycles that have exactly two special edges, modulo (10^9+7).

A simple cycle is a cycle of length at least 3, without repeated vertices or edges.

Constraints

* 2 \leq H \leq 18
* 1 \leq P_i \leq L where L = 2^{H-1}
* P_i \neq P_j (so this is a permutation)

Input

Input is given from Standard Input in the following format (where L = 2^{H-1}).


H
P_1 P_2 \cdots P_L


Output

Compute the sum of products of simple cycles that have exactly two special edges. Print the answer modulo (10^9+7).

Examples

Input

3
2 3 1 4


Output

121788


Input

2
1 2


Output

36


Input

5
6 14 15 7 12 16 5 4 11 9 3 10 8 2 13 1


Output

10199246
#include <bits/stdc++.h>

using namespace std;

typedef long long lol;
const int N = 1 << 19;
const int mod = 1e9 + 7;
inline int pls( int a , int b ) { a += b - mod; return a + ( a >> 31 & mod ); }
inline int mns( int a , int b ) { a -= b; return a + ( a >> 31 & mod ); }
inline void inc( int & a , int b ) { a += b - mod; a += a >> 31 & mod; }
inline void dec( int & a , int b ) { a -= b; a += a >> 31 & mod; }
inline int fpow( int base , int k ) {
  int res = 1;
  while( k ) {
    if( k & 1 ) res = (long long)res * base % mod;
    base = (long long)base * base % mod; k >>= 1;
  }
  return res;
} int _w;

int n , lg , p[N] , ans , bac[N];

int dist( int u , int v ) {
  if( u < v ) swap( u , v );
  int res = u;
  while( u != v ) {
    u >>= 1;
    res = (lol)res*u%mod;
  }
  return res;
}
  
void upd( int u , int w , bool flag ) {
  while( u ) {
    w = (lol)w * u % mod;
    if( flag ) dec( bac[u] , w );
    else inc( bac[u] , w );
    u >>= 1;
  }
}

void qry( int u , int w ) {
  int lb = 0;
  while( u ) {
    inc( ans , (lol)w * bac[u] % mod );
    dec( ans , (lol)w * lb % mod * u % mod );
    lb = bac[u];
    w = (lol)w * u % mod;
    u >>= 1;
  }
}

int inv[N];

void solve( int u , int l , int r ) {
  if( r == l ) return;
  int mid = ( l + r ) >> 1; 
  for( int i = l ; i <= mid ; ++i ) 
    upd( p[i] , dist( i , u ) , 0 );
  for( int i = mid + 1 ; i <= r ; ++i )
    qry( p[i] , (lol)dist( i , u ) * inv[u] % mod );
  for( int i = l ; i <= mid ; ++i )
    upd( p[i] , dist( i , u ) , 1 );
  solve( u << 1 , l , mid );
  solve( u << 1 | 1 , mid + 1 , r );
}

int main( void ) {
  _w = scanf("%d",&lg);
  n = ( 1 << lg );
  inv[1] = 1;
  for( int i = 2 ; i < N ; ++i )
    inv[i] = (lol)(mod-mod/i)*inv[mod%i]%mod;
  for( int i = ( 1 << ( lg - 1 ) ) ; i < n ; ++i )
    _w = scanf("%d",p+i) , p[i] += ( 1 << ( lg - 1 ) ) - 1;
  solve( 1 , ( 1 << ( lg - 1 ) ) , n - 1 );
  cout << ans;
  return 0;
}
