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 pair< int , int >PII;
const int MOD = 1e9+7;

int sum(int a, int b) {
    return a + b >= MOD ? a + b - MOD : a + b;
}
int sub(int a, int b) {
    return a - b < 0 ? a - b + MOD : a - b;
}
int mul(int a, int b) {
    return (1LL*a*b)%MOD;
}
int pw(int a, int b) {
	if (!b) return 1;
	int r = pw(a, b/2);
	r = mul(r, r);
	if (b%2) r = mul(r, a);
	return r;
}

const int MAXH = 20;
int p[1<<MAXH];
int sm[1<<MAXH];

void jogKoro(int u, int upore) {
//    cout << "jog " << u << " " << upore << endl;
    while (u > 1) {
        upore = mul(upore, u);
        u >>= 1;
//        cout << "add " << upore << " to " << u << endl;
        sm[u] = sum(sm[u], upore);
    }
}
void biyogKoro(int u, int upore) {
    while (u > 1) {
        upore = mul(upore, u);
        u >>= 1;
        sm[u] = sub(sm[u], upore);
    }
}

int L;
int ans;

vector< PII >solve(int u, int l, int r) {
    if (l==r) {
        vector< PII >v = {{p[l]+L-1, u}};
        return v;
    }

    int mid = l+(r-l+1)/2;
    vector< PII >bam = solve(u*2, l, mid-1);
    vector< PII >dan = solve(u*2+1, mid, r);

//    cout << "at " << u << endl;
//    cout << "bam:";
//    for (int x : bam) cout << " " << x;
//    cout << endl;
//    cout << "dan:";
//    for (int x : dan) cout << " " << x;
//    cout << endl;

    for (PII q : bam) {
        jogKoro(q.first, q.second);
    }

    for (PII q : dan) {
//        cout << "for " << i << endl;
        int w = q.first;
        int upore = mul(q.second, mul(u, w));

        while (w > 1) {
            upore = mul(upore, w>>1);
//            cout << (w>>1) << " upore: " << upore << " bam: " << sub(sm[w>>1], mul(sm[w], w)) << endl;
//            cout << "adds: " << mul(upore, sub(sm[w>>1], mul(sm[w], w))) << endl;
            ans = sum(ans, mul(upore, sub(sm[w>>1], mul(sm[w], w))));
            w >>= 1;
        }
    }

    for (PII q : bam) {
        biyogKoro(q.first, q.second);
    }

    vector< PII >total;
    for (PII q : bam) total.emplace_back(q.first, mul(q.second, u));
    for (PII q : dan) total.emplace_back(q.first, mul(q.second, u));
    return total;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int H;
    cin >> H;

    L = 1<<(H-1);
    for (int i = 1; i <= L; i++) cin >> p[i];
    solve(1, 1, L);

    cout << ans << "\n";

    return 0;
}
