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
///****In the name of ALLAH, most Gracious, most Compassionate****//

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

#define ALL(a) a.begin(), a.end()
#define FastIO ios::sync_with_stdio(false); cin.tie(0);cout.tie(0)
#define IN freopen("input.txt","r+",stdin)
#define OUT freopen("output.txt","w+",stdout)

#define DBG(a) cerr<< "line "<<__LINE__ <<" : "<< #a <<" --> "<<(a)<<endl
#define NL cout<<endl

template < class T1,class T2>
ostream &operator <<(ostream &os,const pair < T1,T2 > &p)
{
    os<<"{"<<p.first<<","<<p.second<<"}";
    return os;
}

const int N=3e5+5;
const ll oo=1e9+7;

int p[N];


vector<int > child[N][2];


ll Tree[N];

void update(int idx, ll x,int n)
{
	// Let, n is the number of elements and our queries are
	// of the form query(n)-query(l-1), i.e range queries
	// Then, we should never put N or MAX in place of n here.
	while(idx<=n)
	{
		Tree[idx]= (Tree[idx] + x) % oo;
		idx+=(idx&-idx);
	}
}

ll query(int idx)
{
	ll sum=0;
	while(idx>0)
	{
		sum = (sum + Tree[idx]) % oo;
		idx-=(idx&-idx);
	}
	return sum;
}

ll root_to_node[N];
ll root_to_node_inv[N];

ll extended_euclidean(ll a, ll b, ll & x, ll & y) {
    if (a == 0) {
        x = 0;
        y = 1;
        return b;
    }
    ll x1, y1;
    ll d = extended_euclidean(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return d;
}
ll mod_inverse(ll a,ll m)
{
    ll x, y;
    ll g = extended_euclidean(a, m, x, y);
    if (g != 1)
    {
        cout << "No solution!";
        return -1;
    }
    else
    {
        x = (x % m + m) % m;
        return x;
    }
}


int32_t main()
{
    FastIO;
    int h;
    cin>>h;
    int l = 1<<h-1;
    for(int i=1;i<=l;i++)
        cin>>p[i];
    for(int i=1;i<=l;i++)
    {

        int u = l +i -1;
        bool par = u % 2;
        int p = u/2;


        do
        {

            child[p][par].push_back(i);
            par = p % 2;
            p = p/2;
        }
        while(p);

    }

    root_to_node[0] =1;
    root_to_node_inv[0] =1;

    int total_node = (1<<h)-1;
    for(int i=1;i<=total_node;i++)
        root_to_node_inv[i] = mod_inverse(root_to_node[i] = (root_to_node[i/2] * i) % oo , oo);

    ll ans = 0;

    for(int lca=1;lca<l;lca++)
    {

        for(int leaf: child[lca][0])
        {
            ll g = root_to_node[l+ leaf-1] * root_to_node_inv[lca]% oo;
            g = (g * root_to_node[l+ p[leaf] - 1 ]) % oo;
            update(p[leaf] , g, l);
        }

        for(int leaf : child[lca][1])
        {
            ll g = root_to_node[l+leaf - 1] * root_to_node_inv[lca/2]% oo;
            int u = l + p[leaf] - 1;
            int par = u % 2;
            int  p = u/2;

            g = (g * u) % oo;
            g = (g * p) % oo;

            do
            {


                ll now = (query(child[p][!par].back()) - query(child[p][!par].front() - 1) )% oo;



                now  = now * root_to_node_inv[p] % oo;


                now = (now * g) %oo;

                ans = (ans + now) % oo;



                par  = p%2;
                p/=2;

                g= (g * p) %oo;
            }
            while(p);
        }


        for(int leaf: child[lca][0])
        {
            ll g = root_to_node[l+ leaf-1] * root_to_node_inv[lca] % oo;
            g = (g * root_to_node[l+ p[leaf] - 1 ]) % oo;
            update(p[leaf] , -g, l);
        }
    }

    ans = (ans  + oo) % oo;

    cout<<ans<<"\n";

}
