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<iostream>
#define DIM (1 << 18 + 5)
#define mod 1000000007
using namespace std;
int n, k, i, sol;
int p[DIM], d[DIM];
void solve(int nod, int prod){
    prod = prod * 1LL * nod % mod;
    if(nod < k){
        solve(2 * nod, prod);
        solve(2 * nod + 1, prod);
        return;
    }
    int u, prod2, sum;
    prod2 = prod;
    for(u = p[nod]; u != 1; u /= 2){
        prod2 = prod2 * 1LL * u % mod;
        sum = d[u / 2] - d[u] * 1LL * (u / 2) % mod;
        if(sum < 0){
            sum += mod;
        }
        sol = (sol + sum * 1LL * prod2) % mod;
    }
}
void clean(int nod){
    if(nod < k){
        clean(2 * nod);
        clean(2 * nod + 1);
    }
    else{
        for(int u = p[nod]; u != 0; u /= 2){
            d[u] = 0;
        }
    }
}
void calc(int nod, int prod){
    prod = prod * 1LL * nod % mod;
    if(nod < k){
        calc(2 * nod, prod);
        calc(2 * nod + 1, prod);
        return;
    }
    for(int u = p[nod]; u != 0; u = u / 2){
        prod = prod * 1LL * u % mod;
        d[u] = (d[u] + prod) % mod;
    }
}
int main(){
    cin>> n;
    k = (1 << (n - 1) );
    for(i = k; i < 2 * k; i++){
        cin>> p[i];
        p[i] = p[i] + k - 1;
    }
    for(i = 1; i < k; i++){
        calc(2 * i, i);
        solve(2 * i + 1, 1);
        clean(2 * i);
    }
    cout<< sol;
}
