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>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <bitset>
#include <random>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
clock_t __my_start_clock = clock();
#else
#define eprintf(...)
#endif

#define TIMESTAMP(x) eprintf("["#x"] Time : %.3lf s.\n", (clock() - __my_start_clock)*1.0/CLOCKS_PER_SEC)
#define TIMESTAMPf(x,...) eprintf("[" x "] Time : %.3lf s.\n", __VA_ARGS__, (clock() - __my_start_clock)*1.0/CLOCKS_PER_SEC)

#define db(x) cerr << #x << " = " << x << endl
#define db2(x, y) cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")\n";
#define db3(x, y, z) cerr << "(" << #x << ", " << #y << ", " << #z << ") = (" << x << ", " << y << ", " << z << ")\n"
#define dbv(a) cerr << #a << " = "; for (auto xxxx: a) cerr << xxxx << " "; cerr << endl


using namespace std;

#ifdef LOCAL
static struct __timestamper {
    string what;
    __timestamper(const char* what) : what(what){};
    __timestamper(const string& what) : what(what){};
    ~__timestamper(){
        TIMESTAMPf("%s", what.data());
    }
} __TIMESTAMPER("end");
#else
struct __timestamper {};
#endif

typedef long long ll;
typedef long double dbl;

const int MOD = (int)1e9 + 7;

void add(int &x, ll y) {
    x = (x + y) % MOD;
}

int mul(int x, int y) {
    return 1LL * x * y % MOD;
}

int solve(int h, vector<int> p) {
    int k = 1 << (h - 1);
    assert((int)p.size() == k);

    int n = 1 << h;
    vector<int> L(n), R(n);
    for (int i = 0; i < k; i++) L[k + i] = R[k + i] = i;
    for (int i = k - 1; i >= 1; i--) {
        L[i] = L[2 * i];
        R[i] = R[2 * i + 1];
    }

    vector<int> sum(n);
    auto enable = [&](int x, int prod) {
        x += k;
        while (x > 0) {
            prod = mul(prod, x);
            add(sum[x], prod);
            x >>= 1;
        }
    };

    vector<int> cprod(k);
    for (int i = 0; i < k; i++) cprod[i] = k + i;

    int ans = 0;
    for (int v = k - 1; v >= 1; v--) {
        for (int i = L[v * 2 + 1]; i <= R[v * 2 + 1]; i++) {
            enable(p[i], cprod[i]);
        }

        for (int i = L[v * 2]; i <= R[v * 2]; i++) {
            int oth = k + p[i];

            int rprod = mul(mul(v, cprod[i]), oth);
            while (oth > 1) {
                int pr = oth >> 1;
                rprod = mul(rprod, pr);
                add(ans, mul(rprod, sum[oth ^ 1]));
                oth = pr;
            }
        }

        for (int i = L[v * 2 + 1]; i <= R[v  * 2 + 1]; i++) {
            enable(p[i], mul(cprod[i], MOD - 1));
        }

        for (int i = L[v]; i <= R[v]; i++) cprod[i] = mul(cprod[i], v);
    }
    return ans;
}

int main() {
#ifdef LOCAL
    freopen("in", "r", stdin);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int h;
    while (cin >> h) {
        int k = 1 << (h - 1);
        vector<int> p(k);
        for (int i = 0; i < k; i++) {
            cin >> p[i];
            p[i]--;
        }

        cout << solve(h, p) << endl;
    }

    return 0;
}
