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;

const int maxH = 18;
int ans, H, L, N, v[(1 << maxH) + 10], konst[(1 << maxH) + 10], invv[(1 << maxH) + 10], p[(1 << maxH) + 10];
const int mod = 1e9 + 7;

int add (int x, int y) {int ans = x + y; if (ans >= mod) ans -= mod; return ans;}
int subtract (int x, int y) {if (x >= y) return x - y; return x - y + mod;}
int mul (int x, int y) {return 1LL * x * y % mod;}
void adto (int &x, int y) {x += y; if (x >= mod) x -= mod;}

int power (int a, int b)
{
    int p = 1;
    for (int i=0; (1<<i) <= b; i++)
    {
        if (b & (1 << i)) p = mul (p, a);
        a = mul (a, a);
    }
    return p;
}

/*int fac[2000009], inv[2000009];
void Prec (int lim){fac[0] = inv[0] = 1;for (int i=1; i<=lim; i++)fac[i] = mul (fac[i - 1], i);
inv[lim] = power (fac[lim], mod - 2);for (int i=lim - 1; i>=0; i--)inv[i] = mul (inv[i + 1], i + 1);}
int comb (int N, int K){if (K > N || N < 0 || K < 0) return 0; int ans = mul (fac[N], inv[N - K]);ans = mul (ans, inv[K]);return ans;}*/

vector < vector < int > > aint, sums;

void printVector (vector < int > &v, string s)
{
    for (auto it : v)
        printf ("%d ", it);
    printf ("%s", s.c_str ());
}

int countInBetween (int node, int minVal, int maxVal)
{
    //printf ("%d [%d, %d]\n", node, minVal, maxVal);
    //printVector (aint[node], "\n");
    //printVector (sums[node], "\n");
    auto it2 = lower_bound(aint[node].begin (), aint[node].end (), maxVal + 1);
    auto it1 = lower_bound(aint[node].begin (), aint[node].end (), minVal);
    if (it1 == aint[node].end ())
        return 0;
    /*printf ("%d\n", *aint[node].begin ());
    printf ("%d\n", *it1);*/
    int pos2 = (int) (it2 - aint[node].begin ()) - 1, pos1 = it1 - aint[node].begin ();
    if (pos1 <= pos2)
    {
        if (pos1 == 0) return sums[node][pos2];
        return subtract (sums[node][pos2], sums[node][pos1 - 1]);
    }
    return 0;
}

int getRange (int node, int descendant, int d)
{
    int rg = ((node * 2) + 1) << (d - 1);
    if (rg > descendant)
        return node << 1 | 1;
    return node << 1;
}

void Read (int &x);

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

Read (H), L = (1 << (H - 1));
v[1] = 1, invv[0] = invv[1] = 1;
for (int i=2; i < (1 << H); i++)
    v[i] = mul (v[i / 2], i),
    invv[i] = power (v[i], mod - 2);
aint.resize (2 * L);
sums.resize (2 * L);
for (int i=1; i<=L; i++)
    Read (p[i]),
    aint[L + i - 1] = {p[i] + L - 1},
    konst[p[i]] = mul (v[i + L - 1], v[p[i] + L - 1]),
    sums[L + i - 1] = {konst[p[i]]};
for (int i=L - 1; i>1; i--)
{
    int f1 = i << 1, f2 = f1 | 1;
    aint[i].resize (aint[f1].size () + aint[f2].size ());
    merge (aint[f1].begin (), aint[f1].end (), aint[f2].begin (), aint[f2].end (), aint[i].begin ());
    sums[i].resize (aint[i].size ());
    sums[i][0] = konst[aint[i][0] - L + 1];
    for (int j=1; j<aint[i].size (); j++)
        sums[i][j] = add (sums[i][j - 1], konst[aint[i][j] - L + 1]);
}
/*for (int i=1; i<2 * L; i++, printf ("\n"))
    for (auto it : aint[i])
        printf ("%d ", it);*/
for (int i=1; i<=L; i++)
{
    int x = i + L - 1, y = p[i] + L - 1;
    for (int ex = 1; ex<H; ex++)
        for (int ey = 1; ey<H; ey++)
        {
            int x2 = x >> ex, y2 = y >> ey;
            int curr = getRange (y2, y, ey);
            if (curr != y2 * 2)
                continue;
            int xtra = konst[p[i]];
            xtra = mul (xtra, mul (invv[x2 >> 1], invv[x2]));
            xtra = mul (xtra, mul (invv[y2 >> 1], invv[y2]));
            //printf ("%d %d (%d %d) ", x, y, x2, y2);
            int sum = countInBetween (getRange (x2, x, ex), curr << (ey - 1), ((curr + 1) << (ey - 1)) - 1);
            //printf (" -> %d\n", sum);
            //printf ("+ %d\n\n", mul (sum, xtra));
            adto (ans, mul (sum, xtra));
        }
}
//printf ("%d\n", ans);
printf ("%d\n", ans);
return 0;
}

const int maxl = 100000;
char buf[maxl];
int pntr = maxl - 1;

void Next ()
{
    if (++pntr == maxl)
        fread (buf, 1, maxl, stdin), pntr = 0;
}

void Read (int &x)
{
    while (buf[pntr] < '0' || buf[pntr] > '9') Next ();
    for (x = 0; buf[pntr] >= '0' && buf[pntr] <= '9'; Next ()) x = x * 10 + buf[pntr] - '0';
}
