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 llint;
typedef pair <int, int> pi;

const int MAXN = 1 << 19;
const int MOD = 1e9 + 7;

int n, h, ofs, sol;
int p[MAXN], uk[MAXN];
int t[MAXN * 4], val[MAXN * 4], inv[MAXN * 4];

int add (int x, int y) {x += y; if (x >= MOD) return x - MOD; return x;}
int sub (int x, int y) {x -= y; if (x < 0) return x + MOD; return x;}
int mul (int x, int y) {return (llint) x * y % MOD;}

int pot (int x, int e) {
    if (e == 0) return 1;
    int t = pot(x, e / 2);
    t = mul(t, t);
    if (e & 1) t = mul(t, x);
    return t;
}

void upd (int pos, int val) {
    pos += ofs;
    t[pos] = val;
    pos /= 2;
    while (pos > 0) {
        t[pos] = add(t[pos * 2], t[pos * 2 + 1]);
        pos /= 2;
    }
}

void dfs (int x, int curr) {
    inv[x] = pot(curr, MOD - 2);
    curr = mul(curr, x);
    inv[x] = mul(inv[x], pot(curr, MOD - 2));
    val[x] = curr;
    if (x < ofs) {
        dfs(2 * x, curr);
        dfs(2 * x + 1, curr);
    }
}

int calc (int x, int lo, int hi, int pos) {
    int mid = (lo + hi) / 2;
    if (lo == hi) return 0;
    if (pos <= mid) return add(calc(2 * x, lo, mid, pos), mul(t[2 * x + 1], inv[x]));
    return add(calc(2 * x + 1, mid + 1, hi, pos), mul(t[2 * x], inv[x]));
}

void solve (int x, int lo, int hi) {
    if (lo >= hi) return;
    int mid = (lo + hi) / 2;
    for (int i = mid + 1; i <= hi; i++) upd(p[i], uk[i]);
    for (int i = lo; i <= mid; i++) sol = add(sol, mul(calc(1, 0, ofs - 1, p[i]), mul(uk[i], inv[x])));
    for (int i = mid + 1; i <= hi; i++) upd(p[i], 0);
    solve(2 * x, lo, mid);
    solve(2 * x + 1, mid + 1, hi);
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> h;
    n = (1 << h), ofs = n / 2;
    dfs(1, 1);
    for (int i = 0; i < ofs; i++) {
        cin >> p[i];
        p[i]--;
        uk[i] = mul(val[i + ofs], val[p[i] + ofs]);
    }
    solve(1, 0, ofs - 1);
    cout << sol;
    return 0;
}
