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
#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

//defines
typedef long long ll;
typedef long double ld;
#define TIME clock() * 1.0 / CLOCKS_PER_SEC
#define prev _prev
#define y0 _y0
#define kill _kill

//permanent constants
const ld pi = acos(-1.0);
const int day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int digarr[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
const int dxo[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dyo[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
const int alf = 26;
const int two = 2;
const ld eps = 1e-8;
const ll INF = (ll)(1e18 + 239);
const int BIG = (int)(2e9 + 239);
const int MOD = 1e9 + 7;
const ll MOD2 = (ll)MOD * (ll)MOD;

//random
#ifdef ONPC
mt19937_64 rnd(239);
#else
mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

//constants
const int M = (int)(2e5 + 239);
const int N = (int)(2e3 + 239);
const int L = 20;
const int T = (1 << 20) + 239;
const int B = 500;
const int X = (1 << 18) + 239;

int power(int a, int k)
{
    if (k == 0)
        return 1;
    int t = power(a, k >> 1);
    t = 1LL * t * t % MOD;
    if (k & 1)
        t = 1LL * t * a % MOD;
    return t;
}

int used[X], cnt_used;

int sred[X], sblack[X];
int mult[X], dv[X];
int a[X];

int ans;

int h, k;

vector<pair<int, int>> dfs(int p)
{
    if (p >= (1 << (h - 1)))
        return {make_pair(a[p - (1 << (h - 1))], 1LL * p * mult[a[p - (1 << (h - 1))]] % MOD)};
    vector<pair<int, int>> ired = dfs(2 * p);
    vector<pair<int, int>> iblack = dfs(2 * p + 1);
    /*cerr << p << "!!!\n";
    for (pair<int, int> t : ired)
        cerr << t.first << " " << t.second << "r\n";
    for (pair<int, int> t : iblack)
        cerr << t.first << " " << t.second << "b\n";*/
    for (pair<int, int>& t : ired)
        t.second = 1LL * t.second * p % MOD;
    cnt_used++;
    vector<int> now;
    for (pair<int, int> t : ired)
    {
        int x = t.first;
        while (true)
        {
            if (used[x] != cnt_used)
                now.push_back(x);
            used[x] = cnt_used;
            sred[x] += t.second;
            if (sred[x] >= MOD)
                sred[x] -= MOD;
            if (x == 1)
                break;
            x /= 2;
        }
    }
    for (pair<int, int> t : iblack)
    {
        int x = t.first;
        while (true)
        {
            if (used[x] != cnt_used)
                now.push_back(x);
            used[x] = cnt_used;
            sblack[x] += t.second;
            if (sblack[x] >= MOD)
                sblack[x] -= MOD;
            if (x == 1)
                break;
            x /= 2;
        }
    }
    int cs = 0;
    for (int t : now)
        if (t < (1 << (h - 1)))
        {
            int cur = 1LL * sred[2 * t] * sblack[2 * t + 1] % MOD;
            cur += 1LL * sred[2 * t + 1] * sblack[2 * t] % MOD;
            if (cur >= MOD)
                cur -= MOD;
            cs += 1LL * cur * dv[t] % MOD;
            if (cs >= MOD)
                cs -= MOD;
        }
    ans += cs;
    if (ans >= MOD) ans -= MOD;
    //cerr << p << " " << cs << "\n";
    for (int t : now)
    {
        sred[t] = 0;
        sblack[t] = 0;
    }
    for (const auto& t : iblack)
        ired.push_back(make_pair(t.first, 1LL * t.second * p % MOD));
    return ired;
}

int32_t main()
{
#ifdef ONPC
    freopen("input", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> h;
    mult[0] = 1;
    mult[1] = 1;
    for (int i = 2; i < (1 << h); i++)
        mult[i] = 1LL * mult[i / 2] * i % MOD;
    for (int i = 1; i < (1 << h); i++)
        dv[i] = power(1LL * mult[i] * mult[i / 2] % MOD, MOD - 2);
    for (int i = 0; i < (1 << (h - 1)); i++)
    {
        cin >> a[i];
        a[i] += (1 << (h - 1)) - 1;
    }
    ans = 0;
    dfs(1);
    cout << ans << "\n";
    return 0;
}