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>
#define pb push_back
#define pll pair <ll, ll>
#define mp make_pair
#define pyshnapyshnakaa ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define x first
#define y second
#pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
#define plll pair <pair <ll, ll>, ll>
#define pllll pair <pair <ll, ll>, pair <ll, ll> >
#define psl pair <string, ll>
#define pld pair <ld, ld>
#define all(a) a.begin(), a.end()
#define vvl vector <vector <ll> >
#define cld complex <double>

typedef long long ll;

typedef long double ld;

using namespace std;

const ll maxn = 1e6 + 100;
const ll mod = 1e9 + 7;

ll n, m, k, t, h;

ll st2[maxn];

ll ans = 0;

ll P[maxn];

ll mark[maxn];

vector <ll> to_clear;

void dfs2(ll v, bool left, ll product, ll last) {
    // cout << "DFS2 " << v << endl;
    ll nproduct = product * (v) % mod;
    if (left) {
        to_clear.pb(v);
        mark[v] += product;
        mark[v] %= mod;
    }
    else {
        ll dans = nproduct * (mark[v] - mark[last] * last % mod + mod) % mod;
        // cout << v << " DANS " << dans << endl;
        ans += dans;
        ans %= mod;
    }
    if (v == 1) {
        return;
    }
    dfs2(v / 2, left, nproduct, v);
}

void dfs1(ll v, bool left, ll product) {
    // cout << "V " << v << endl;
    ll nproduct = product * (v) % mod;
    if (v > n - m) {
        ll to = n - m + P[v - (n - m) - 1] + 1; 
        // cout << "FROM " << v << " TO " << to << endl;
        dfs2(to, left, nproduct, 0);
        return;
    }
    dfs1(2 * v, left, nproduct);
    dfs1(2 * v + 1, left, nproduct);
}

void work(ll v) {
    // cout << "WORK " << v << endl;
    ll q;
    dfs1(v * 2, 1, v);
    dfs1(v * 2 + 1, 0, 1);
    for (auto v : to_clear) {
        mark[v] = 0;
    }
    to_clear.clear();
}

int main() {
    pyshnapyshnakaa
    ll q, w, e, a, b, c;
    st2[0] = 1;
    for (q = 1; q < 63; q++) {
          st2[q] = st2[q - 1] * 2;
    }
    cin >> h;
    m = st2[h - 1];
    n = st2[h] - 1;
    for (q = 0; q < m; q++) {
        cin >> P[q];
        P[q]--;
    }
    for (q = 1; q <= n - m; q++) {
        work(q);
    }
    cout << ans;
    return 0;
}